백준, BOJ, 1926번 C++ [CPP]

이 문제도

이전 문제와 형제문제라고 할 정도로 BFS의 기본을 알려준다

[프로그래밍언어(Programming Language)/C || C++] - 백준, BOJ, 2178번 C++ [CPP]

www.acmicpc.net/problem/1926

1926번: 그림

 

---

 

바로 이 문제가 BFS가 탐색한 노드의 수를 알려주는 것인데

뭐 메모리랑 관련이 있다고만 해두겠다.

**사실 큐에 쌓이는 노드가 더 메모리랑 관련있지만..뭐 그렇다.

 

---

 

# 맞는 풀이

 

#include<iostream>
#include <queue>

using namespace std;

#define X first
#define Y second 

    int dx[4] = {1,0,-1,0};
    int dy[4] = {0,1,0,-1};
    int board[501][501];
    int vis[501][501];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    queue<pair<int,int>> q;
    int n, m;
    cin>> n >> m;
    
    int num = 0; //그림 개수
    int M = 0; // 그림 최댓값
    
    // 주어진 그림 저장.
    for(int i = 0; i<n; i++){
        for(int j = 0; j<m; j++){
            cin >> board[i][j];
        }
    }
    
    //그림 뒤지면서 조사(0,0)
    for(int i = 0; i<n; i++){
        for(int j = 0; j<m; j++){
            if(board[i][j] == 1 && vis[i][j] != 1){
                int width = 0;// 새로운 그림을 조사하기 위해서 초기화
                vis[i][j] = 1; //방문함
                num++;
                width++;
                q.push({i,j}); //푸시
                while(!q.empty()){
                    pair<int,int> cur = q.front(); q.pop();
                    for(int dir = 0; dir < 4; dir++){ // 상하좌우 칸을 살펴볼 것이다.
                      int nx = cur.X + dx[dir];
                      int ny = cur.Y + dy[dir]; // nx, ny에 dir에서 정한 방향의 인접한 칸의 좌표가 들어감
                      if(nx < 0 || nx >= n || ny < 0 || ny >= m) 
                          continue; // 범위 밖일 경우 넘어감
                      if(vis[nx][ny] || board[nx][ny] != 1)
                          continue; // 이미 방문한 칸이거나 파란 칸이 아닐 경우
                      vis[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
                      q.push({nx,ny});
                      width++;
                    }
                }
                if(M <= width){
                    M = width;
                }
            }
        }
    }

    cout << num << "\n" << M;
}

 

미로가 동시에 여러개 주어진 것이라고 봐도 되는데

즉, 미로가 몇개이고 가장 넓은 미로는 무엇인가? 라고 봐도 된다.

 

조건을 잘 정리해야 쉽게 접근이 가능하다.

 

크게 이 3가지가 문제푸는데 중요하다

1. 그림의 전체를 뒤진다. (for문 2개가 쓰인 이유)

 

2. 방문한 곳을 저장하여 방문한 곳은 가지 않는다.

(if문으로 visit이면 전체를 뒤지더라도 visit은 탐색하지 않음)

 

3. 탐색이 더 이상 진행되지 않으면 1개의 미로 조사 끝