[Beakjoon] 1926_그림

문제이해

그림이 그려져 있음

• 그림의 개수
  그림은 1로 연결된 것을 한 그림이라고 정의
  가로나 세로로 연결 -> 그림O
  대각선으로 연결 -> 그림X
• 그림의 넓이
  그림에 포함된 1의 개수

입력
도화지의 세로 크기 : n (1 <= n <= 500)
도화지의 가로 크기 : m (1 <= m <= 500)
첫째 줄 n m
둘째 줄 ~ n+1 그림의 정보

출력
그림의 개수
그림 중 넓이가 가장 넓은 것의 넓이
(그림이 하나도 없는 경우 -> 가장 넓은 그림의 넓이 0

STL BFS DFS를 사용해서 풀어보자!
BFS vs DFS
BFS (너비 우선 탐색)
시작 정점으로부터 가가운 정점을 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
너비 우선탐색을 위해 가까운 거리에 있는 정점들을 차례로 저장하고, 들어간 순서대로 꺼낼 수 있는 자료구조가 필요하다. 큐(queue)를 사용한다.

push 정점 -> 시작 정점 확인할 때 큐에 정점 삽입(아직 방문하지 않음)
pop 정점 -> 정점을 방문할 때 큐에서 정점 삭제(방문함)
push 인접 정점 -> 방문한 정점과 인접한 정점 확인할 때 큐에 삽입(아직 방문하지 않음)

정점들이 방문될 때마다 큐에 인접한 정점을 삽입한다.
더 이상 방문할 인접 정점이 없는 경우 -> 큐의 맨 앞에서 정점을 꺼내 그 정점과 인접한 정점들을 차례대로 방문한다.

넓이 우선 탐색으로 깊이가 아닌 넓이를 우선시한다. 시작 정점으로 부터 가까운 정점을 방문하고 가장 멀리 즉 깊이 있는 정점은 가장 나중에 방문한다.

• 2차원 배열을 이용해서 입력받은 그림을 넣는다. -> 그림의 크기 또한 입력받기 떄문에 동적 배열로 작성해야할 것 같다.
• 시작지점 0,0위치로 부터 그림이 될 수 있는 후보인 가로나 세로만 탐색한다. -> 시작지점이 되는 기준이 있을까? 시작지점이 1이 아닌 0일 경우?
• 탐색하면서 그림의 개수를 c변수로 선언해 그림을 발견하면 c++을 해준다. -> 전역변수로 선언해야 될 듯하다.
• 탐색하면서 그림의 넓이를 b변수 = 1로 초기화한 후 그림의 영역을 찾을 떄마다 b++을 해준다. -> 지역변수로 탐색하는 반복문 안에 선언해 준다. 가장 큰 넓이를 가지는 b_b변수 = 1를 전역 변수로 초기화해 반복문 마지막에 하나의 그림의 최종 넓이가 b_b변수의 값보다 큰 경우 갱신해준다.
• STL BFS는 안해봤음.. -> 구글링...

STL BFS

BFS는 한 정점에서 갈라지는 갈래를 하나하나 넓게 탐색하는 방법이다. 큐를 사용해 구현한다..? 큐 안에 주변에 탐색할

코드

하나의 그림만을 확인하는 코드

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

#define X first // pair에서 first, second를 줄여서 쓰기 위해서 사용
#define Y second  // first -> X, second- > Y

int board[502][502];
bool visited[502][502]; // 해당 칸을 방문했는지 여부를 저장

int n, m; // n = 행의 수, m = 열의 수
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 }; // 상하좌우 네 방향을 의미

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    queue<pair<int, int> > Q; // 큐를 좌표형태로 하기 위해 pair사용
    for (int i = 0; i < n; i++) { // 한 행씩 받는다.
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }

    visited[0][0] = 1; // (0,0) 시작지점을 방문했다고 표시
    Q.push({ 0,0 }); // 큐에 (0,0)시작점 삽입
    
    while (!Q.empty()) { // 큐가 빌 때까지 상하좌우 확인
        pair<int, int> cur = Q.front(); // 큐의 front를 cur에 저장
        Q.pop(); // 큐의 front를 pop한다.
        cout << '(' << cur.X << ", " << cur.Y << ") -> "; // pop하는 값 확인
        for (int dir = 0; dir < 4; dir++) { // 상하좌우 칸을 확인한다.
            // 순서대로 하(1,0) 우(0,1) 상(-1,0) 좌(0,-1) 
            //          x-1,y
            //  x,y-1   x,y     x,y+1
            //          x+1,y
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) { // 범위 밖으로 벗어가는 경우
                continue;
            }
            if (visited[nx][ny] || board[nx][ny] != 1) { // 이미 방문 or 방문하지 못함 경우
                continue;
            }
            visited[nx][ny] = 1; // (nx,ny)를 방문했다고 표시
            Q.push({ nx,ny }); // 큐에 (nx,ny)삽입
        }
    }
   
}

위의 코드 후에 다음 그림을 찾는 과정을 추가하고 반복한다.

해결

• 2차원 배열을 이용해서 입력받은 그림을 넣는다. -> 그림의 크기 또한 입력받기 떄문에 동적 배열로 작성해야할 것 같다.
  BFS를 구현하기 위한 QUEUE와 2차원의 그림을 구현하기 위해 pair를 사용한다.
  queue<pair<int, int> > Q;

• 시작지점 0,0위치로 부터 그림이 될 수 있는 후보인 가로나 세로만 탐색한다. -> 시작지점이 되는 기준이 있을까? 시작지점이 1이 아닌 0일 경우?

• 탐색하면서 그림의 개수를 c변수로 선언해 그림을 발견하면 c++을 해준다. -> 전역변수로 선언해야 될 듯하다.

• 탐색하면서 그림의 넓이를 b변수 = 1로 초기화한 후 그림의 영역을 찾을 떄마다 b++을 해준다. -> 지역변수로 탐색하는 반복문 안에 선언해 준다. 가장 큰 넓이를 가지는 b_b변수 = 1를 전역 변수로 초기화해 반복문 마지막에 하나의 그림의 최종 넓이가 b_b변수의 값보다 큰 경우 갱신해준다.

• STL BFS는 안해봤음.. -> 구글링...