벽 부수고 이동하기 4

문제

이미지 클릭

문제 설명

• 배열에서 1의 경우에는 이동할 수 없는 벽이 있는 곳이고 0이 있는 경우는 이동할 수 있는 곳을 의미한다.
• 한 칸의 벽을 부수고 이동할 수 있는 부분을 구해준다.

문제 해설

• 처음에는 벽을 하나씩 부수면서 이동할 수 있는 공간을 모두 탐색하는 방식으로 문제를 해결하려고 하였지만 이럴 경우에는 시간초과가 발생할 가능성이 높기 때문에 다른 방법으로 접근해야 했다.

1. 모든 칸을 확인하면서 방문하지 않고 이동할 수 있는 부분부터 탐색을 시작한다.
2.  그 칸부터 이동할 수 있는 부분이 몇 군데 있는지를 확인 해준다.
3. 이때 칸을 방문할 때 연결된 칸들은 같은 숫자로 체크해 주고 연결되지 않은 부분은 다른 숫자로 체크해 준다.
4. 그 칸을 방문하면서 체크했던 숫자를 인덱스로 하여서 이동할 수 있는 칸의 개수를 저장해 준다.
5. 그런 다음 모든 칸을 확인하면서 이번에는 이동할 수 없는 부분을 방문하여서 상하좌우를 탐색해 준다. 이전에 방문 체크 해주었던 숫자를 통해서 이동할 수 있는 부분의 크기를 확인해 준다.

방문 체크 예시

방문 체크 한 부분에 대한 이동 칸 개수 저장

설명을 이해하기 힘들기 때문에 코드를 살펴보면서 이해하는 것이 제일 좋다.

최종 코드

#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;
int n, m;
int a[1004][1004];
int visited[1004][1004];
int gs[1000004];
const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
int main() {
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < m; j++) a[i][j] = s[j] - '0';
  }
  int cnt = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (a[i][j] == 0 && visited[i][j] == 0) {
        queue<pair<int, int>> q;
        q.push({i, j});
        visited[i][j] = cnt;
        int size = 0;
        while (!q.empty()) {
          int x = q.front().first, y = q.front().second;
          q.pop();
          size+=1;
          for (int d = 0; d < 4; d++) {
            int xx = x + dx[d], yy = y + dy[d];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && a[xx][yy] == 0 && !visited[xx][yy]) {
              visited[xx][yy] = cnt;
              q.push({xx, yy});
            }
          }
        }
        gs[cnt] = size;
        cnt++;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (a[i][j] == 1) {
        set<int> s;
        int mov = 1;
        for (int d = 0; d < 4; d++) {
          int xx = i + dx[d], yy = j + dy[d];
          if (xx >= 0 && xx < n && yy >= 0 && yy < m && !a[xx][yy]) {
            int cnt = visited[xx][yy];
            if (s.find(cnt) == s.end()) {
              mov += gs[cnt];
              s.insert(cnt);
            }
          }
        }
        cout << mov % 10;
      } 
      else cout << 0;
    }
    cout << '\n';
  }
}

 

코드에서 살펴보아야 하는 부분은 두 가지 부분이다.

• 모든 칸을 돌아보면서 방문처리와 연결된 부분의 크기 저장해 주기

int cnt = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (a[i][j] == 0 && visited[i][j] == 0) {
        queue<pair<int, int>> q;
        q.push({i, j});
        visited[i][j] = cnt;
        int size = 0;
        while (!q.empty()) {
          int x = q.front().first, y = q.front().second;
          q.pop();
          size+=1;
          for (int d = 0; d < 4; d++) {
            int xx = x + dx[d], yy = y + dy[d];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && a[xx][yy] == 0 && !visited[xx][yy]) {
              visited[xx][yy] = cnt;
              q.push({xx, yy});
            }
          }
        }
        gs[cnt] = size;
        cnt++;
      }
    }
  }

 

기본적인 BFS탐색이지만 방문처리와 이동할 수 있는 칸의 수를 저장해 주는 부분에서 차이가 있다.

• cnt: 서로 연결된 부분들은 cnt로 방문 처리를 해주어야 한다. 그리고 BFS탐색이 끝났다면 cnt를 +1해 주고 또 이동할 수 있는 칸을 찾으면서 연결되지 않은 부분은 서로 다른 숫자로 채워주어야 한다.
• visited 배열: cnt로 방문처리를 해준다.
• size: 연결된 칸들의 크기를 카운트해준다.
• gs 배열: gs [cnt]=size, 즉 방문 처리를 해준 cnt 값에 대한 크기를 gs배열에 저장해 준다.

예시를 들어보자면 다음과 같다.

4 5
11001
00111
01010
10101

 

• 이동할 수 있는 칸인 (0,2)부터 탐색을 시작한다.
• (0,2)와 (0,3)은 visited배열에 1로 체크가 되고 gs배열에는 gs [1]=2의 형태로 저장된다.
• cnt를 +1해 주면서 다음 이동할 수 있는 부분을 탐색해 준다.
•  벽이 있는 칸, 즉 이동할 수 없는 칸을 탐색해 주기

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (a[i][j] == 1) {
        set<int> s;
        int mov = 1;
        for (int d = 0; d < 4; d++) {
          int xx = i + dx[d], yy = j + dy[d];
          if (xx >= 0 && xx < n && yy >= 0 && yy < m && !a[xx][yy]) {
            int cnt = visited[xx][yy];
            if (s.find(cnt) == s.end()) {
              mov += gs[cnt];
              s.insert(cnt);
            }
          }
        }
        cout << mov % 10;
      } 
      else cout << 0;
    }
    cout << '\n';

 

• s: 상하좌우를 탐색하면서 visited배열에 체크된 숫자들을 저장해 주는 역할을 한다. s는 체크된 숫자들이 반복되는지 판단하는 데 사용된다
• mov: gs배열에 저장되어 있는 이동할 수 있는 크기를 모두 더해준다.

이러한 과정을 통해서 mov를 출력해 주면서 이동가능한 칸의 크기를 저장해 준다.

이미지 클릭