[백준/c++] 1926 - 그림

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

1926번: 그림

---

 

1) 풀이

BFS (너비우선탐색)을 이용하여 풀면 되는 문제다. 

BFS에 대한 설명은 아래 3) 참고자료를 참고하길 바란다.

 

BFS 문제 중에서도 딱히 어려운 난이도는 아니라 그것만 안다면 쉽게 풀 수 있다!

여기에서 1로 연결된 것을 그림이라고 하는데, 그 그림의 개수와 그 중 가장 큰 넓이를 출력하면 된다.

 

1. 제일 먼저 탐색을 시작할 좌표를 찾는다. (값이 1인 좌표를 찾아서 시작해야 한다)

2. 해당 좌표를 방문했다는 표시를 하고 탐색을 위한 queue에 push 한다

3. queue가 빌 때까지 queue의 front의 상하좌우를 확인한 뒤(물론 front 값을 다른 변수에 저장하고 pop해준다) 값이 1인 좌표를 계속 queue에 push 한다

(좌표가 그림의 범위를 벗어나거나, 1이 아니거나, 방문했다면 push 하지 않고 넘어간다)

4. queue 가 비는 순간에는 그림이 끝난 것, 즉 1이 더이상 이어져있지 않다는 의미이므로 다음 그림을 찾는다

(1의 과정으로 돌아간다)

 

4의 과정이 끝난 후, 다시 1번의 과정으로 가기 전에 우리는 하나의 그림을 탐색하는것을 마쳤으므로 그림의 개수를 1 늘려주고, 해당 그림의 넓이를 가장 큰 넓이를 구하는 변수에 넣어준다. (max 함수를 이용하여 구한다)

 

이렇게만 하면 문제는 풀어지지만, 개인적으로 추가해두고 싶은 것이 있다!

BFS 알고리즘으로 처음 문제를 풀어볼 때, 개인적으로 상하좌우 탐색할 때의 x,y 좌표가 굉장히 헷갈렸다.

보통 x,y 좌표를 쉽게 반복문으로 돌리기 위해서 그 좌표들을 미리 배열로 선언해놓는데 배열에 집어넣을 때 좌표가 굉장히 헷갈리더라, 왜인지는 모르겠지만! 

그래서 이참에 그림으로 그려놓아보았다.

그림판으로 그려서 엉망진창.. 그래두 이해만 되면 됐징

가운데에 있는 x,y 를 queue의 front 즉 상하좌우 탐색의 기준점? 기준 좌표? 라고 생각해볼 때

그 좌표의 바로 위 좌표는 y에 1을 더한 것, 오른쪽 좌표는 x에 1을 더한 것... 으로 생각하면 된다.

이것만 머리속에 잘 생각하고 있으면, 다음부터는 그냥 자동으로 손이 코드를 치고 있다😁

포스팅 하는 시각이 새벽이라 굉장히 횡설수설한데,, 설명을 모르거나 헷갈리는 부분이 있다면 댓글로 알려주시면 감사하겠습니당!

 

2) 최종 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
int n;
int m;
int cx[4] = { 0,1,0,-1 }; //차례대로 상,우,하,좌 의 X 좌표 (시계방향)
int cy[4] = { 1,0,-1,0 };  // 차례대로 상, 우, 하, 좌 의 y 좌표 (시계방향)
bool used[502][502]; //탐색했는지 여부를 파악
using namespace std;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	int maxim = 0; //가장 넓은 넓이

	vector<vector<int>>v; //이차원 벡터
	for (int i = 0; i < n; i++) {
		vector<int>temp;
		for (int j = 0; j < m; j++) {
			int t;
			cin >> t;
			temp.push_back(t);
		}
		v.push_back(temp);
	}
	queue<pair<int, int>>q; //이차원 벡터의 좌표를 저장할 큐
	int num = 0; //그림의 개수
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (v[i][j] != 1 || used[i][j]) continue; //해당 좌표가 1이 아니거나 방문했다면
			used[i][j] = 1;
			q.push({ i,j });
			int cnt = 0;
			while (!q.empty()) { //하나의 그림이 끝날 때까지. 즉, 더이상 이어져있는 1이 없을떄까지
				pair<int, int>cur = q.front();
				q.pop();
				for (int k = 0; k < 4; k++) { //상하좌우 탐색
					int dx = cur.first + cx[k];
					int dy = cur.second + cy[k];
					if (dx < 0 || dx >= n || dy < 0 || dy >= m) continue; //그림의 범위 벗어나면
					if (used[dx][dy] || v[dx][dy] != 1) continue;
					used[dx][dy] = 1;
					q.push({ dx,dy });
				}
				cnt++;
			}
			maxim = max(maxim, cnt); //max 함수를 이용하여 가장 큰 넓이 구함
			num++; //그림의 개수
		}
	}
	cout << num << '\n' << maxim;

}

3) 참고자료

https://coding-factory.tistory.com/612