[백준] 2665 미로만들기

2665번: 미로만들기

 

www.acmicpc.net

풀이

BFS문제이다. 이동하면서 방의 색을 바꾼다는 점에서 일반적인 문제들과는 차이가 있다 . 일반적인 BFS 문제에서 방문 여부를 확인하던 방식으로 해서는 해결되지 않는다. 검은방을 최소로 바꾸고 끝방으로 가야 하므로 기존에 방문했던 방에 더 적은 수의 검은방을 바꾼 상태로 재 방문할 수 있기 때문이다. 따라서 방문 여부를 체크하는 방식을 수정해야한다. visited[y][x]를 x, y까지 이동하면서 바꾼 검은 방의 수로 정의하여 해결하였다.

그리고 문제에서 방의 정보에 대한 입력값이 띄어쓰기가 되어있지 않으므로 cin이 아닌 scanf("%1d", &map[i][j])를 사용해서 1자리씩 입력받았다.

코드

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

int n;
int map[51][51];
vector<vector<int>> visited;
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };

void bfs() {
    // 방문 여부 체크 배열을 큰 값으로 초기화
    visited = vector<vector<int>>(n + 1, vector<int>(n + 1, 987654321));
    queue<pair<int, int>> q;
    q.push({ 1, 1 });
    visited[1][1] = 0;

    while (!q.empty()) {
        int x = q.front().first; int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i]; int ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
            // 검은 방의 경우 새로 방문할 위치가 현재 위치+1 보다 큰 경우에 방문
            if (map[ny][nx] == 0 && visited[ny][nx] > visited[y][x] + 1) {
                visited[ny][nx] = visited[y][x] + 1;
                q.push({ nx, ny });
            }
            // 흰색 방의 경우 새로 방문할 위치가 현재 위치보다 큰 경우에 방문
            else if (map[ny][nx] == 1 && visited[ny][nx] > visited[y][x]) {
                visited[ny][nx] = visited[y][x];
                q.push({ nx, ny });
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%1d", &map[i][j]);

    bfs();
    printf("%d\n", visited[n][n]);
    return 0;
}