반응형
알고리즘 분류 : BFS
늑대가 가지 못하는 위치를 찾는 문제다. 갈 수 있는 곳을 모두 탐색해야 하므로, BFS를 사용하면 된다.
- 늑대(W)는 여러 마리가 주어질 수 있고, 각 늑대는 맵에 갈 수 있는 모든 곳을 가야 한다.
- 늑대의 이동을 크게 2가지로 구분해서 처리해야 한다.
- 1. 다음 이동 위치가 초원('.')인 경우
- 초원에서는 인접한 상하좌우로 한 칸씩 움직인다.
- 움직인 후 방문 체크를 하고, 큐에 좌표를 집어넣는다.
- 2. 다음 이동 위치가 초원('.')이 아닌 경우 : 산('#'), 빙판('+')
- while 반복문을 통해 늑대를 이동시켜야 한다.
- 1) 이동한 곳이 산이라면, 위치를 되돌리고 반복문을 빠져나온다.
- 2) 산이 아니라면 빙판이므로, 다음 좌표로 한 칸 앞으로 간다.
- 3) 다음 이동 좌표가 초원이라면, 반복문을 빠져나온다. 아니라면 1) ~ 2) 과정을 산에 부딪히거나, 초원에 도착할 때까지 반복한다.
- 반복문을 빠져나온 후, 현재 좌표를 방문 체크하고 큐에 집어넣는다.
C++ 소스코드
#include <cstdio> #include <queue> using namespace std; struct wolf { int x, y; }; int n, m; char a[100][100]; bool check[100][100]; queue<wolf> q; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; void bfs() { while (!q.empty()) { int x = q.front().x, y = q.front().y; q.pop(); for (int i=0; i<4; i++) { int nx = x+dx[i], ny = y+dy[i]; if (a[nx][ny] == '.' && !check[nx][ny]) { q.push({nx, ny}); check[nx][ny] = true; } else { while (a[nx][ny] != '.') { if (a[nx][ny] == '#') { nx -= dx[i], ny -= dy[i]; break; } nx += dx[i], ny += dy[i]; } if (!check[nx][ny]) { q.push({nx, ny}); check[nx][ny] = true; } } } } } int main() { scanf("%d %d", &n, &m); for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { scanf(" %1c", &a[i][j]); if (a[i][j] == 'W') { q.push({i, j}); check[i][j] = true; } } } bfs(); for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { if (a[i][j] == '.' && !check[i][j]) printf("P"); else printf("%c", a[i][j]); } printf("\n"); } return 0; }
Python 3 소스코드
from collections import deque n, m = map(int, input().split()) a = [list(input().strip()) for _ in range(n)] check = [[False]*m for _ in range(n)] dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1) q = deque() def bfs(): while q: x, y = q.popleft() for i in range(4): nx, ny = x+dx[i], y+dy[i] if a[nx][ny] == '.' and not check[nx][ny]: q.append((nx, ny)) check[nx][ny] = True else: while a[nx][ny] != '.': if a[nx][ny] == '#': nx, ny = nx-dx[i], ny-dy[i] break nx, ny = nx+dx[i], ny+dy[i] if not check[nx][ny]: q.append((nx, ny)) check[nx][ny] = True for i in range(n): for j in range(m): if a[i][j] == 'W': q.append((i, j)) check[i][j] = True bfs() for i in range(n): for j in range(m): if a[i][j] == '.' and not check[i][j]: print("P", end='') else: print(a[i][j], end='') print()
참고
- 백준 온라인 저지 : BOJ 16441
반응형