BOJ - 1926번, 그림 문제 DFS를 이용한 풀이

이번 문제는 DFS 태그가 걸려있는 문제를 찾다가, 풀게된 1926번 문제 정리입니다.

오랜만에 풀어서 그런지 이상한 부분에서 실수가 많았다.

문제 자체는 전형적인 DFS로 해결할 수 있는 간단한 문제였는데, 잘못 생각한 부분들이 있어 오답 처리를 받게된 부분을 정리해보려고 합니다.

 

1926번: 그림

---

문제

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

입력

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

출력

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

예제 입력 

6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

예제 출력 

4
9

---

풀이 과정 설명

우선 다음과 같이 전형적인 DFS 알고리즘을 사용해 주어진 도화지 정보를 탐색하도록 구현했습니다.

전형적인 DFS 방식의 풀이

이렇게 풀어서 정답 처리를 받을 수 있었지만, 처음 풀이를 진행할 때에는 visited를 이용한 방문 처리와 여기서 단순하게 true or false를 저장하지 말고, 누적하면서 그림의 너비 정보를 같이 저장해서 메모리를 아껴보자라고 생각하고 풀이를 진행했습니다.

 

그러나, 이 방식은 결국 온전하게 그림의 너비 정보를 담기에 문제가 있었습니다.

// 대략 이런 느낌으로 코딩했습니다.

visited[next x][next y] = visited[x][y] + 1;

왜냐하면, DFS 방식으로 잘 탐색해서 최댓값으로 그림의 너비를 잘 뽑아내면, 아주 좋겠지만 모든 경우 이렇게 할 수 없기 때문입니다.

 

대표적으로 방문 상황에서 해당 경로가 막혀 다시 돌아갔는데, 돌아간 지점에서는 이전 그림의 너비에 +1을 해서 너비를 측정하는 잘못된 방식을 취했었기 때문입니다.

 

추가로 이번에는 inRange 함수를 이용한 도화지 내의 지점인지에 대한 확인 과정을 매크로 함수를 정의해서 해결하는 두 가지 방식으로 풀이를 진행 해봤습니다.

// 원래는 이렇게 함수로 사용
bool inRange(int x, int y) {
	return (0 <= x && x < n && 0 <= y && y < m);
}

// 이렇게 매크로를 정의해서도 똑같이 사용 가능합니다.
#define inrange(x, y) (0 <= x && x < n && 0 <= y && y < m)

---

매크로 함수란?

 

매크로 함수는 함수처럼 인자를 설정할 수 있는 매크로를 의미한다고 합니다.

MAX 같은 사례가 그냥 매크로를 사용한 경우

위의 그림에서 inrange 함수가 x, y를 인자로 하는 매크로 함수라고 정리할 수 있습니다.

 

사실 함수의 선언과 비슷하지만, 완전히 같은 것은 아닙니다.

• 매크로 함수는 단순 치환을 진행한다.
• 매크로 함수는 인자의 자료형을 신경쓰지 않는다.
• 이를 자료형의 독립성을 보장한다고 한다.
• 또한 함수와 다르게 재귀적 호출이 불가능하다.
• 매크로는 컴파일 과정에서 매크로 이름을 가진 것들이 지정해놓은 값으로 mapping되어 컴파일됩니다.

이렇게 이번 문제에서 매크로 함수까지 새로이 사용 해봤습니다.

---

제출한 소스 코드 (C++)

#include <iostream>
#define MAX 501
#define inrange(x, y) (0 <= x && x < n && 0 <= y && y < m)

using namespace std;

int n, m;	// n: height, m: width
int arr[MAX][MAX];
bool visited[MAX][MAX];

int maxDrawingWidth = 0;
int drawingWidth = 1;

bool inRange(int x, int y) {
	return (0 <= x && x < n && 0 <= y && y < m);
}

/***
* x, y: start position of dfs
*/
void dfs(int x, int y) {
	int dx[] = { -1, 1, 0, 0 };
	int dy[] = { 0, 0, -1, 1 };

	maxDrawingWidth = (maxDrawingWidth > drawingWidth) ? maxDrawingWidth : drawingWidth;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		// 도화지를 벗어나거나, 이미 방문한 칸인 경우 건너띈다.
		if (!inrange(nx, ny) || visited[nx][ny])
			continue;

		if (arr[nx][ny] == 1) {
			//visited[nx][ny] = visited[x][y] + 1;
			visited[nx][ny] = true;

			drawingWidth++;
			dfs(nx, ny);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	int drawingCnt = 0;

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visited[i][j] || arr[i][j] == 0)
				continue;

			visited[i][j] = true;
			drawingCnt++;
			dfs(i, j);
			drawingWidth = 1;
		}
	}

	cout << drawingCnt << '\n' << maxDrawingWidth;

	return 0;
}