본문 바로가기

C++

 (64)
[백준] 9019번: DSLR (C++ 풀이) 문제 https://www.acmicpc.net/problem/9019풀이BFS로 D, S, L, R에 대해 탐색하고 찾으려는 값이 제일 처음 나오는 것이 그 값을 찾는 가장 빠른 방법이다. 주의해야할 점이 자리수 관련해서 문제이해를 초반에 못했었는데,1을 L하면 10이 되고, R하면 1000이 된다. 마찬가지로 11을 L하면 110이 되고, R하면 1001이 된다. 세자리수도 마찬가지이다.그리고 나는 큐에 지나온 경로를 string으로 저장했었는데 이 과정에서 string 복사가 시간을 많이 잡아먹었다.string복사를 줄이고 나니 시간초과에 걸리지 않았다. 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/9019.cpp결과
[백준] 2636번: 치즈 (C++ 풀이) 문제 https://www.acmicpc.net/problem/2636풀이1. BFS로 치즈가 있는 칸의 개수 세기 -> 0이면 반복 종료2. BFS로 치즈 녹이기 1번 BFS는 치즈(1)을 기준으로 탐색을 했고, 2번 BFS는 빈칸(0)을 기준으로 탐색을 했다.둘다 단지번호 붙이기 문제처럼 접근해서 풀었다. 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/2636.cpp결과
[백준] 2644번: 촌수계산 (C++ 풀이) 문제 https://www.acmicpc.net/problem/2644풀이 BFS로 간단히 풀 수 있었는데 괜히 유니온파인드 비슷한거 도전했다가 틀리기만 했다.. 아마도 어떠한 예제에서는 되지 않았을 것이다ㅠㅠX에서 시작해서 가능한 모든 정점을 방문해서 거리를 저장해놓는다. 처음에 dist배열을 -1로 초기화해두었다. BFS를 하고 나면 dist[y]를 출력하면 되는데 이때, 방문하지 못한(부모가 다른) 곳을 출력하는 경우 -1이다. 코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/2644.cpp결과
[백준] 17069번: 파이프 옮기기2 (C++ 풀이) 문제 https://www.acmicpc.net/problem/17069풀이블로그 풀이를 보았다...파이프 옮기기1과 같은 문제인데 범위만 다른 문제이다파이프 옮기기1은 N이 16까지라면 이것은 32까지다. 같은 코드를 제출했더니 메모리초과가 떴다.DFS+DP 방법으로 풀었다.dp는 3차원 long long 배열이다. 예제를 보면 출력 답이 int 범위를 넘는 것을 알 수 있다.dp[a][b][c] = d의 의미 : (a, b)에서 c방향으로의 탐색을 했는데 (n-1, n-1)까지 갈 수 있는 경우의 수가 d이다.dp값을 -1로 초기화해놓는다. 그 이유는 -1이 아직 방문하지 않음을 뜻하고0은 목적지에 갈 수 있는 경우가 없다는 뜻!목적지에 도착하면 1을 리턴한다! 그러면 재귀가 순서대로 빠지면서 경로에..
[백준] 17070번: 파이프 옮기기1 (C++ 풀이) 문제 https://www.acmicpc.net/problem/17070풀이블로그 보면서 풀었다.BFS로 완전탐색하는 방식으로 해결했다.1. (0,0),(0,1)에서 시작해서 파이프 끝이 (n-1, n-1)이면 도착한것!2. 파이프 두칸을 가지고 탐색하지 않고 끝점과 현재 진행방향을 고려했다.3. 큐에 (x, y, 진행방향) 이렇게 세가지 정보가 들어간다.4. 진행방향이 가로 또는 세로면, 그대로 진행하거나 대각선 이동하면 되고   진행방향이 대각선이면, 가로, 세로, 대각선 이동을 해야한다.5. 대각선 이동을 할때에는 (x, y+1)과 (x+1, y)가 0인지도 확인해야한다.6. (x, y)가 (n-1, n-1)이면 ans를 1증가시키고 다음으로 넘어간다. (총 방법의 개수를 세는 것이기 때문)코드 h..
[백준] 11403번: 경로 찾기 (C++ 풀이) 문제풀이dfs탐색을 통해 풀었다.한 행씩 탐색하면서 갈 수 있는 길마다 체크하고, 체크되어있는곳만 1을 출력하는 방법으로 프린트했다.가는 길이 있고 아직 가지 않은 정점이면 방문하고 dfs 타고 들어가는 방식으로 구현했다.코드결과
[백준] 3055번: 탈출 (C++ 풀이) 문제풀이고슴도치가 몰려오는 물을 피해 목적지를 달성한다는 점에서 불 문제와 비슷하다. [백준] 5427번: 불 ☜풀이 가기1. bfs로 물을 먼저 이동시켰다. 물이 이동한 시간을 배열에 따로 저장해놓는다.'.'이랑 'S'가 있는 곳만 이동할 수 있도록 했다.2. 물을 다 이동시킨 후, bfs로 고슴도치를 이동시켰다. 마찬가지로 고슴도치의 이동시간을 다른 배열에 따로 저장해놓는다. '.'과 'D'가 있는 곳으로 이동시킬 수 있는데, 이때 '.'일 경우, 물 보다 먼저 도달하는지 체크해야한다. 즉, 물이 왔다간 시간보다 고슴도치가 왔다가는 시간이 작아야 하거나 물이 왔다간 적이 없어야 한다.3. 입력받을 때, 'D'의 좌표를 따로 저장해놓은 다음에 출력할때 고슴도치 배열의 해당 좌표 값이 -1이면 탈출하지 ..
[백준] 13913번: 숨바꼭질4 (C++ 풀이) 문제풀이기존의 숨바꼭질[1697]에서 나온 결과를 토대로 dfs로 다시 타고 들어가는 작업을 했더니 시간초과가 났다,,(ㅠㅠ당연한결과,,)bfs하면서 큐에 push할때 따로 parent배열에 부모를 저장해놓고,목적지에 도착하면 parent를 따라 올라가는 방식으로 해결했다.코드결과

티스토리툴바