알고리즘
BOJ 16509 · 장군
알고리즘 분류 : BFS 장기 말을 옮기는 최소 횟수를 구하는 문제다. BFS를 통해 상(象)을 옮겨서 왕을 먹어야 한다. 장기판에서 상을 옮겨서 왕의 위치로 도달하는 최소 횟수를 구해야 한다.상은 그림처럼 움직이며, 움직이는 경로에 다른 말이 있으면 해당 위치로 옮길 수 없다. 다른 말은 존재하지 않기 때문에, 왕의 위치가 상의 이동 경로에 있는지만 고려하면 된다.별도로 이동 좌표를 만들고, 움직이는 경로에 왕이 있다면 상을 움직이지 않는다.이동이 가능하다면 옮긴다. C++ 소스코드 #include #include #include using namespace std; struct grid { int x, y; }; int sx, sy, ex, ey; int dist[10][9]; const int dx..
BOJ 16469 · 소년 점프
알고리즘 분류 : BFS 세 명의 사람이 한곳에 모이는 최단 거리와, 그 최단 거리의 수를 구해야 하는 문제다. 주어진 3명의 좌표를 큐에 집어넣고, 각각 BFS를 돌리면 된다. 3명의 사람을 0번, 1번, 2번이라고 하자.dist 배열은 이동 거리를 저장하고, 방문 여부를 체크한다.dist의 인덱스는 [X 좌표] [Y 좌표] [사람 번호] 이다. dist의 모든 값은 -1로 초기화해둔다.큐에 0~2번 사람의 좌표를 모두 넣고, dist[X][Y][번호]를 0으로 초기화한다.BFS를 통해 완전 탐색을 하면, dist 배열에 각 사람의 이동 거리가 업데이트되어있다.dist배열을 N*M 순서로 탐색하면서 dist[X][Y][0], dist[X][Y][1], dist[X][Y][2]의 값이 모두 -1이 아닌 ..
BOJ 16441 · 아기돼지와 늑대
알고리즘 분류 : BFS 늑대가 가지 못하는 위치를 찾는 문제다. 갈 수 있는 곳을 모두 탐색해야 하므로, BFS를 사용하면 된다. 늑대(W)는 여러 마리가 주어질 수 있고, 각 늑대는 맵에 갈 수 있는 모든 곳을 가야 한다. 늑대의 이동을 크게 2가지로 구분해서 처리해야 한다. 1. 다음 이동 위치가 초원('.')인 경우초원에서는 인접한 상하좌우로 한 칸씩 움직인다.움직인 후 방문 체크를 하고, 큐에 좌표를 집어넣는다. 2. 다음 이동 위치가 초원('.')이 아닌 경우 : 산('#'), 빙판('+')while 반복문을 통해 늑대를 이동시켜야 한다.1) 이동한 곳이 산이라면, 위치를 되돌리고 반복문을 빠져나온다.2) 산이 아니라면 빙판이므로, 다음 좌표로 한 칸 앞으로 간다.3) 다음 이동 좌표가 초원이..
BOJ 16397 · 탈출
알고리즘 분류 : BFS 숫자 N을 숫자 G로 만드는 최소 버튼 횟수를 구하는 문제다. BFS를 통해 최소 횟수를 구하면 된다. 숫자 N을 큐에 집어넣는다.현재 숫자를 X라고 할 때, 다음 숫자는 X+1 또는 X*2 - 10^(X*2의 자릿수-1)가 된다.최대 T번까지 BFS로 숫자를 탐색한다.숫자 G에 도달하면 값을 출력한다. C++ 소스코드 #include #include #include #include using namespace std; int n, t, g; int dist[100000]; void bfs() { queue q; q.push({n}); dist[n] = 0; while (!q.empty()) { int x = q.front(); q.pop(); if (dist[x] > t) br..
BOJ 16174 · 점프왕 쩰리 (Large)
알고리즘 분류 : BFS (0, 0)부터 출발하여 점프를 하면서 (N-1, N-1) 도착하는 것을 구현하는 문제다. BFS를 통해 맵을 탐색하면서, 밟은 위치에 쓰여있는 숫자만큼 이동하면 된다. 유사한 문제로 BOJ 16173번 '점프왕 쩰리 (Small)'이 있다. N 범위만 더 적은 문제이므로, 같은 코드로 해결할 수 있다. (0, 0)를 큐에 넣고 BFS를 시작한다.아래 방향(↓)과 오른쪽 방향(→)으로만 이동할 수 있으므로 구현이 간단하다.현재 위치에 쓰여있는 숫자만큼 이동한다.방문 여부를 체크하면서 마지막 좌표(N-1, N-1)까지 이동할 수 있는지 확인한다. C++ 소스코드 #include #include using namespace std; struct jump { int x, y; }; i..
BOJ 14940 · 쉬운 최단거리
알고리즘 분류 : BFS 맵에 주어진 목표지점에서 각 지점에 대한 거리를 구하는 문제다. BFS를 통해 각 점에 대한 최단 거리를 모두 출력하면 된다. N*M 사이즈의 맵에서 목표지점(2)로부터 각 지점까지의 최단 거리를 구한다.벽(0)으로는 이동할 수 없다. C++ 소스코드 #include #include using namespace std; struct grid { int x, y; }; int n, m, sx, sy; int a[1000][1000]; const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, 1, -1}; void bfs() { queue q; q.push({sx, sy}); a[sx][sy] = 2; while (!q.empty()) { int x = q...
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