BOJ 5980 · Corn Maze

알고리즘 분류 : BFS  

BFS를 이용하여 미로 탈출을 하는 것을 구현해야 한다. 일반적인 탈출 BFS와 같으나, 맵에서 순간 이동이 가능하다. 순간 이동하는 부분을 잘 처리하는 것이 관건이다.

• 출발점(@)부터 출구(=)까지 도달하는 최단 거리를 구해야 한다.
• 순간 이동(A~Z)는 쌍으로 이루어져 있으며, 이동 비용은 없다.
• 알파벳 총개수(26) 만큼 리스트를 만들어 둔다. 입력받을 때, 대문자 알파벳인 경우 해당 좌표를 리스트에 저장한다.
• BFS를 통해 이동하다가 순간 이동 입구에 도착하면, 리스트에 있는 좌표를 꺼내서 반대편 입구로 넘어간다. 넘어간 곳의 좌표를 큐에 집어넣는다.
• 풀(.)이면 일반적인 이동이 가능하다. 방문 체크를 하고, 이동 좌표를 큐에 집어넣는다.
• 위 과정을 출구에 도착할 때까지 반복한다.

---

C++ 소스코드

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

struct maze {
    int x, y, d;
};

int n, m;
char a[301][301];
bool check[300][300];
vector<maze> v[26];
queue<maze> 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, d = q.front().d; q.pop();
        if (a[x][y] == '=') {
            printf("%d\n", d);
            return;
        }
        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 (check[nx][ny] || a[nx][ny] == '#') continue;
            int c = a[nx][ny]-'A';
            if (0 <= c && c <= 25) {
                if (nx == v[c][0].x && ny == v[c][0].y) {
                    nx = v[c][1].x;
                    ny = v[c][1].y;
                } else {
                    nx = v[c][0].x;
                    ny = v[c][0].y;
                }
            } else {
                check[nx][ny] = true;
            }
            q.push({nx, ny, d+1});
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            char c;
            scanf(" %1c", &c);
            a[i][j] = c;
            if ('A' <= c && c <= 'Z') {
                v[c-'A'].push_back({i, j});
            } else if (c == '@') {
                q.push({i, j, 0});
                check[i][j] = true;
            }
        }
    }
    bfs();
    return 0;
}

---

Python 3 소스코드

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

n, m = map(int, input().split())
a = [list(input().strip()) for _ in range(n)]
check = [[False]*m for _ in range(n)]
v = [[] for _ in range(26)]
q = deque()

def bfs():
    while q:
        x, y, d = q.popleft()
        if a[x][y] == '=':
            print(d)
            return
        for dx, dy in (-1,0), (1,0), (0,-1), (0,1):
            nx, ny = x+dx, y+dy
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if not check[nx][ny] and a[nx][ny] != '#':
                k = ord(a[nx][ny])-65
                if 0 <= k <= 25:
                    if len(v[k]) != 2:
                        continue
                    if (nx, ny) == v[k][0]:
                        nx, ny = v[k][1]
                    else:
                        nx, ny = v[k][0]
                else:
                    check[nx][ny] = True
                q.append((nx, ny, d+1))

for i in range(n):
    for j in range(m):
        c = a[i][j]
        if 'A' <= c <= 'Z':
            v[ord(c)-65].append((i, j))
        elif c == '@':
            q.append((i, j, 0))
            check[i][j] = True
bfs()

---

참고

• 백준 온라인 저지 : BOJ 5980