프로그래밍/알고리즘

BOJ 16441 · 아기돼지와 늑대

반응형


알고리즘 분류 : 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()




참고



반응형