프로그래밍/알고리즘

BOJ 11567 · 선진이의 겨울 왕국

반응형


알고리즘 분류 : BFS  


빙판길 탈출 가능 여부를 구현하는 문제다. 빙판길은 손상되지 않은 상태(.)와 손상된 상태(X)가 있다. 초기 위치는 항상 손상된 상태로 주어지며, 탈출구는 손상시켜서 빙판을 없애야 한다. BFS를 통해 맵을 탐색하고, 탈출구 부분은 왔다 갔다 하면서 무너뜨려서 탈출해야 한다.


  • 출발 좌표를 (SX, SY), 도착 좌표를 (EX, EY)라 하자.
  • (SX, SY)부터 BFS 탐색을 진행하면서, 다음 이동 좌표가 (EX, EY)인지 확인해야 한다.

  • 1. 만약 (EX, EY)라면, 손상되지 않은 상태(.)인지 손상된 상태(X)인지 확인해야 한다.
  • 손상되지 않은 상태라면, 한 번 밟은 것이므로 손상된 상태로 바꾼다. 도착 좌표를 큐에 집어넣는다.
  • 손상된 상태라면, 탈출이 가능한 것이므로, "YES"를 출력하고 종료한다.

  • 2. 만약 (EX, EY)가 아닌 위치라면, 일반적인 이동을 해야 한다.
  • 손상된 상태(X)의 빙판으로는 이동할 수 없다.
  • 손상되지 않은 상태(.)의 빙판이라면, 이동한다. 빙판을 밟았으므로, 손상된 상태(X)로 바꾼다.





C++ 소스코드


#include <cstdio>
#include <queue>
using namespace std;

struct ice {
    int x, y;
};

int n, m, sx, sy, ex, ey;
char a[501][501];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void bfs() {
    queue<ice> q;
    q.push({sx-1, sy-1});
    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 (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (nx == ex-1 && ny == ey-1) {
                if (a[nx][ny] == '.') {
                    a[nx][ny] = 'X';
                    q.push({nx, ny});
                } else {
                    printf("YES\n");
                    return;
                }
            } else if (a[nx][ny] != 'X') {
                q.push({nx, ny});
                a[nx][ny] = 'X';
            }
        }
    }
    printf("NO\n");
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) scanf("%s", a[i]);
    scanf("%d %d", &sx, &sy);
    scanf("%d %d", &ex, &ey);
    bfs();
    return 0;
}




Python 3 소스코드


from collections import deque
from sys import stdin
input = stdin.readline

def bfs():
    q = deque()
    q.append((sx-1, sy-1))
    while q:
        x, y = q.popleft()
        for dx, dy in (-1,0), (1,0), (0,1), (0,-1):
            nx, ny = x+dx, y+dy
            if 0 <= nx < n and 0 <= ny < m:
                if nx == ex-1 and ny == ey-1:
                    if a[nx][ny] == '.':
                        a[nx][ny] = 'X'
                        q.append((nx, ny))
                    else:
                        print("YES")
                        return
                elif a[nx][ny] != 'X':
                    q.append((nx, ny))
                    a[nx][ny] = 'X'
    print("NO")

n, m = map(int, input().split())
a = [list(input().strip()) for _ in range(n)]
sx, sy = map(int, input().split())
ex, ey = map(int, input().split())
bfs()




참고



반응형