전체
BOJ 14923 · 미로 탈출
알고리즘 분류 : BFS 벽을 하나 뚫고 미로를 탈출하는 것을 구현해야 한다. BOJ 2206번 '벽 부수고 이동하기'와 유사한 문제이다. 입력으로 주어진 출발점(HX, HY)부터 탈출 위치(EX, EY)까지 BFS 탐색을 통해 이동한다.이동 거리 저장과 방문 여부를 체크할 배열 dist를 3차원 배열로 선언한다.dist의 인덱스는 [X 좌표] [Y좌표] [벽 부순 횟수] 이다.벽(1)을 만나면, 벽을 아직 부수지 않은 경우 벽을 부수고 이동한다. 벽을 이미 부순 경우 이동하지 않는다.빈칸(0)은 그대로 이동한다. C++ 소스코드 #include #include #include using namespace std; struct maze { int x, y, z; }; int n, m, hx, hy, ex..
BOJ 14716 · 현수막
알고리즘 분류 : DFS 현수막에 쓰여있는 문자의 개수를 출력하는 문제다. 전형적인 플러드 필 문제이며, 인접한 8방향을 처리하면 된다. M*N 사이즈의 맵을 DFS로 탐색하면서 연결된 글자(1)를 따라 이동하면 된다.인접한 8방향(상, 하, 좌, 우, 대각선)으로 이동한다.글자의 개수를 카운트한다. C++ 소스코드 #include int m, n, ans; int a[250][250]; bool check[250][250]; const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}; const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1}; void dfs(int x, int y) { check[x][y] = true; for (int i=0; i
BOJ 14496 · 그대, 그머가 되어
알고리즘 분류 : BFS 야민정음을 통해 A 문자를 B 문자로 치환할 때, 최소 치환 횟수를 구하는 문제다. 인접 리스트 기반의 BFS 문제로 보면 된다. 입력으로 주어지는 치환 문자쌍을 인접 리스트로 만든다.문자 A부터 BFS 탐색을 시작하여 문자 B까지 도달하는 최소 횟수를 구하면 된다. C++ 소스코드 #include #include #include #include using namespace std; int a, b, n, m; vector v[1001]; int dist[1001]; void bfs() { queue q; q.push(a); dist[a] = 0; while (!q.empty()) { int x = q.front(); q.pop(); if (x == b) { printf("%d\..
BOJ 13903 · 출근
알고리즘 분류 : BFS 출근하기 위해 필요한 최소 걸음을 구하는 문제다. BFS를 통해 최소 횟수를 구하면 된다. 첫 번째 줄부터 시작해서 마지막 줄에 도착하면 출근에 성공한 것이다. 마지막 줄에 도달하지 못하면 출근할 수 없다. 이동 방법이 정해져 있지 않으므로, 이 부분만 잘 구현하면 일반적인 BFS 문제와 비슷하다. R*C 사이즈의 맵을 기준으로, 0번째 줄에서 출발하여 R-1번째 줄에 도착하면 출근이 가능한 것이다.0번째 줄에 있는 세로 블록(1)을 큐에 모두 집어넣는다.입력으로 주어지는 이동 규칙에 따라 이동을 한다. 가로 블록(0)으로는 이동할 수 없다.R-1번째 줄에 도착하면 이동 횟수를 출력하고, 만약 도착할 수 없다면 -1을 출력한다. C++ 소스코드 #include #include u..
BOJ 13700 · 완전 범죄
알고리즘 분류 : BFS S부터 출발하여 D에 도착하는 최소 이동을 구하는 문제다. BFS를 이용하여 구하면 된다. S부터 시작하여 BFS 탐색을 진행한다.현재 위치가 X라 할 때, 다음 위치는 X+F (→이동) 또는 X-B (←이동)이 된다.K개의 경찰서를 제외한 곳으로 이동하면서 최소 이동 횟수를 구하면 된다. C++ 소스코드 #include #include #include using namespace std; int n, s, d, f, b, k; int dist[100001]; void bfs() { queue q; q.push(s); dist[s] = 0; while (!q.empty()) { int x = q.front(); q.pop(); if (x == d) { printf("%d\n", ..
BOJ 13746 · Islands
알고리즘 분류 : DFS 주어진 맵에 존재하는 섬의 최소 개수를 구하는 문제다. 전형적인 플러드 필 문제이다. 맵에서 땅('L')을 시작점으로 하여 DFS 탐색을 한다.구름('C')은 땅 또는 물이 될 수 있으므로, 이동 가능하다.물('W')로는 이동할 수 없다.모든 땅의 탐색이 끝날 때까지 진행한다. C++ 소스코드 #include int r, c, ans; char a[51][51]; bool check[50][50]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; void dfs(int x, int y) { check[x][y] = true; for (int i=0; i
BOJ 13565 · 침투
알고리즘 분류 : BFS 바깥쪽부터 안쪽까지 전류가 침투할 수 있는지 확인하는 것을 구현해야 한다. 바깥쪽은 첫 번째 행이며, 안쪽은 마지막 행이다. 첫 번째 행부터 BFS 탐색을 시작해서 마지막 행에 도달하는지 확인해보면 된다. 0 번째 행에 있는 모든 흰색 격자(0)의 좌표를 큐에 집어넣는다.BFS 탐색을 시작하여 N 번째 행까지 도달하는지 확인한다. 차단 물질(1)로는 이동할 수 없다.N-1 번째 행에 도달하면 전류가 침투 가능한 것이므로 "YES"를 출력하고 탐색을 종료한다.BFS 탐색이 끝날 때까지 N-1 번째 행에 도달하지 못하면, 침투 불가능한 것이므로 "NO"를 출력한다. C++ 소스코드 #include #include using namespace std; struct grid { int ..
BOJ 12273 · Dragon Maze (Large)
알고리즘 분류 : BFS 드래곤이 파워를 모으면서 탈출하는 것을 구현하는 문제다. BFS를 통해 맵을 탐색하면서 구하면 된다. 비슷한 문제로 BOJ 12272번 'Dragon Maze (Small)'이 있다. Small 문제는 Large 문제보다 범위만 적은 것이므로, 같은 코드로 해결 가능하다. 입구에서 출구까지 최단 거리로 이동해야 한다. 단, 정답은 이동하면서 얻은 파워 합의 최댓값이다.따라서 일반적인 큐(Queue)를 쓰는 것보다, 우선순위 큐(Priority Queue)를 이용하는 것이 좋다.이동 거리가 짧을수록, 파워 합이 클수록 우선순위가 높도록 처리한다. 우선순위 큐에 (이동거리, 파워, X 좌표, Y 좌표) 순으로 넣는다.맵을 탐색하면서 위험지역(-1)을 제외한 곳으로 이동한다. 이동한 ..