[BFS]-연습-그림

< BFS > - < 실버 1 >

https://www.acmicpc.net/problem/1926

1926번: 그림

---

[ 1926 ] 그림

 

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

 

:: 입력 ::

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

:: 출력 ::

첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

---

 

가장 큰 크기의 그림을 구하는 과정에서 문제가 있었음 현재 보고있는 그림이 가장 큰 그림이고 그 그림이 이중포문의 거의 마지막에 위치한 경우 원래 내가 적었던 곳에 그림의 크기를 비교하는 구문을 넣으면 내가 미리 설정해둔 if (visit[i][j] == 0 && board[i][j] == 1) 조건에 해당하는 값이 나오지 않으면 가장 큰 그림의 크기와 max 값을 비교하지 못하고 이중포문이 끝나는 경우가 생김 그러니까 비교문이 저 위치에 있으면 마지막 그림의 크기를 비교해보지 않고 끝내게 되는 것 ! 여러 예시를 넣어본 결과 가장 큰 값이 앞에 있으면 잘 돌아감 !

처음에 내가 넣었던 곳에 비교문을 넣은 경우 아래와 같은 결과가 나오게 됨

큰 그림이 뒤에 있는 경우 앞에 있는 4칸 짜리를 최대값으로 뽑아냄

큰 그림이 앞에 있는 경우 최대값이 6으로 잘 나옴

  정답  코드  

 

#include <iostream>
#include <utility> // pair 가 들어있는 헤더
#include <queue>

using namespace std;

int board[501][501];
int visit[501][501];

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

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

	queue<pair<int, int>> q;

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
		}
	}

	//for (int i = 0; i < n; i++) {
	//	for (int j = 0; j < m; j++) {
	//		cout << board[i][j] << " ";
	//	}
	//	cout << "\n";
	//}

	int pic_cnt = 0;
	int pic_size = 0;
	int max_size = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visit[i][j] == 0 && board[i][j] == 1) {
				// if (max_size < pic_size) max_size = pic_size;
				// 해당 비교문이 이 위치에 있으면 해당 조건의 칸이 안 나왔을 때 비교문이 수행되지 않고 이중포문이 끝나버리는 경우가 발생함
				pic_size = 0;
				pic_cnt++;
				visit[i][j] = 1;
				q.push({ i, j });

				while (!q.empty()) {
					pair<int, int> cur = q.front(); q.pop();
					pic_size++;

					for (int dir = 0; dir < 4; dir++) {
						int nx = cur.first + dx[dir];
						int ny = cur.second + dy[dir];

						if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

						if (visit[nx][ny] == 1 || board[nx][ny] != 1) continue;

						visit[nx][ny] = 1;
						q.push({ nx, ny });
						//cout << "push = " << nx << ", " << ny << "\n";
					}
				}
			}
			//cout << "pic_cnt : " << pic_cnt << "\t" << "pic_size : " << pic_size <<"\n";
			if (max_size < pic_size) max_size = pic_size;
		}
	}

	cout << pic_cnt << "\n" << max_size;

}

 

  github 정답  코드  

주석이 다정해서 첨부

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
int board[502][502]; // 1이 파란 칸, 0이 빨간 칸에 대응
bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; // 상하좌우 네 방향을 의미
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++)
      cin >> board[i][j];
  int mx = 0; // 그림의 최댓값
  int num = 0; // 그림의 수
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){ // (i, j)를 시작점으로 하고 싶은 상황
      if(board[i][j] == 0 || vis[i][j]) continue; // 해당 칸이 색칠이 안된 부분(0)이거나 이미 (i, j)를 방문했을 경우 넘어감
      // (i,j)는 새로운 그림에 속해있는 시작점
      num++; // 그림의 수 1 증가
      queue<pair<int,int> > Q;
      vis[i][j] = 1; // (i,j)로 BFS를 시작하기 위한 준비
      Q.push({i,j});
      int area = 0; // 그림의 넓이
      while(!Q.empty()){
        area++; // 큐에 들어있는 원소를 하나 뺄 때 마다 넓이를 1 증가시킴
        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});
        }
      }
      // (i, j)를 시작점으로 하는 BFS가 종료됨
      mx = max(mx, area); // area가 mx보다 클 경우 mx에 area를 대입. max는 STL에 정의된 함수
    }
  }
  cout << num << '\n' << mx;
}

---

1/25 BFS강의 다시보고 다시 문제 풀어봄 이번엔 한번에 성공

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;

int board[501][501];
int visit[501][501];

int dir_x[] = { 0, 1, 0, -1 };
int dir_y[] = { 1, 0, -1, 0 };


int main() {

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int k;
			cin >> k;
			board[i][j] = k;
		}
	}

	queue<pair<int, int>> q;

	int pic_cnt=0;
	int cnt = 0;

	int max_cnt=0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			// 아래 부분에서
			// if (board[i][j] == 0 || visit[i][j] == 1) continue;
			// 이렇게도 조건 처리 가능
			if (board[i][j] == 1 && visit[i][j] == 0) {
				q.push(make_pair(i, j));
				visit[i][j]++;
				pic_cnt++;
			}
			while (!q.empty()) {
				int x = q.front().first;
				int y = q.front().second;
				q.pop();
				cnt++;
				for (int k = 0; k < 4; k++) {
					int nx = x + dir_x[k];
					int ny = y + dir_y[k];
					
					if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
						continue;
					}

					if (board[nx][ny] == 1 && visit[nx][ny] == 0) {
						q.push(make_pair(nx, ny));
						visit[nx][ny]++;
					}
				}
			}

			if (cnt > max_cnt) max_cnt = cnt;
			cnt = 0;
		}
	}


	cout << pic_cnt << "\n" << max_cnt;;
}