[백준] 16946번 벽 부수고 이동하기4

16946 벽 부수고 이동하기4

문제

---

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다

- 벽을 부수고 이동할 수 있는 곳으로 변경한다.

- 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

입력

---

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

---

맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

---

풀이)

BFS를 이용해서 푼 문제이다.

주의할 점은 벽(1)마다 BFS 돌려서 각자 갈 수 있는 칸의 개수를 세면 시간초과가 난다는 점이다.

빈 칸(0)에서 BFS를 돌리면서

인접한 빈 칸들을 묶은 뒤(0을 묶음) 묶은 칸 개수를 한 번에 벽 위치에서 이동 가능한 값에 더해준다.

코드)

#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
 
int N, M;
int map[1000][1000];
int m_cnt[1000][1000];
bool visited[1000][1000];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
queue<pair<int, int>> qu;
vector<pair<int, int>> wall;
 
void bfs(int a,int b) {
    
    qu.push({ a,b });
    visited[a][b] = true;
    
    int cnt = 1; //빈 칸 묶음의 개수
 
    while (!qu.empty())
    {
        int y = qu.front().first;
        int x = qu.front().second;
        qu.pop();
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
            if (visited[ny][nx]) continue;
            visited[ny][nx] = true;
            
            if (map[ny][nx] == 1) { //벽을 만날 경우, 만난 벽의 위치 저장
                wall.push_back({ ny,nx });
            }
            else {//빈 칸일 경우 => 0의 묶음 개수 +1
                cnt++;
                qu.push({ ny,nx });
            }
        }
    }
 
    //만났던 벽에다가 0의 묶음 개수를 더함
    for (int i = 0; i < wall.size(); i++) {
        m_cnt[wall[i].first][wall[i].second] += cnt;
        visited[wall[i].first][wall[i].second] = false; //다른 0 묶음이 이 위치의 벽을 만날수도 있으니깐 이 위치의 벽 방문표시는 초기화
    }
 
    wall.clear();
}
 
int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%1d", &map[i][j]);
            if (map[i][j] == 1) m_cnt[i][j] += 1;//나중에 자기 위치 벽부수면 자신이 그 위치도 움직일 수 있는 공간이니깐 +1 미리 해주기
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!visited[i][j] && map[i][j] == 0) { //0이고 다른 빈 칸 묶음일경우
                bfs(i, j);
            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            printf("%d", m_cnt[i][j] % 10);
        }
        printf("\n");
    }
    return 0;
 
}