Problem

BOJ 1743

코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.

이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다.

통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다.

선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.

Solution

문제 접근 순서

1. 배열에서의 영역들을 탐색하고 영역들의 크기를 구하면서 영역 크기의 최대값을 구하는 문제.
2. dfs 또는 bfs를 사용해서 간단하게 영역의 크기를 구할 수 있음. (dfs사용)
3. 코드 보기 용이하게 class를 사용하여 구현.

문제 풀이

---

dfs

int dfs(int x, int y) {
		int direct[4][2] = { {1,0}, {0,1}, {-1,0}, {0,-1} };
		int size = 1; // 사이즈 증감자

		arr[x][y] = 0; // 노드를 방문했다고 표시

		for (int i = 0; i < 4; i++) {
			int nextX = x + direct[i][0];
			int nextY = y + direct[i][1];

			if (nextX < 1 || nextX > m || nextY < 1 || nextY > n)
				continue;

			//영역을 탐색하면서 1인 경우는 size를 1씩 증가시킴
			if (arr[nextX][nextY] == 1) {
				size += dfs(nextX, nextY);
			}


		}

		//영역의 size 반환
		return size;
	}

1012 양배추 구하기와 매우 유사한 문제였다. 영역의 개수를 구하는 것이 아닌, 제일 큰 영역의 크기를 구하는 문제였다.

dfs를 사용할 때는 탈출 조건이 중요하다. 조건을 적당하게 주어지지 않는다면 이상한 값이 도출되고, 심지어는 빠져나오지 못하게된다.

탈출 조건으로는 방문인자를 사용하는 방법이 있는데 이 문제는 사용하지 않아도 되었다. 노드를 방문하면 0으로 변경해주고 다른 노드를 탐색하도록 하였다. 노드가 1인 경우에만 dfs가 동작하게 되므로 정상적으로 동작하게 된다.

size를 1로 초기화 하였는데, 이는 탐색 할때마다 계속해서 1이 추가되고 결국에는 영역의 크기를 구할 수 있다.

영역의 크기 구하기

int maxArea() {
		int mx = 0; // 최대값

		for (int i = 1; i < n+1; i++) {
			for (int j = 1; j < m+1; j++) {
				//arr이 1일때만 동작
				if (arr[j][i] == 1) {
					//dfs동작
					int tmpArea = dfs(j, i);

					//최대값 갱신
					if ( tmpArea > mx ) {
						mx = tmpArea;
					}
				}
			}
		}

		return mx;
	}

최대값 구하는 것은 별도로 메서드를 만들었다. 특별한 것이 없고 1일때만 동작하도록 조건을 걸어주고 dfs를 마치면 최대값을 점검하여 갱신하게 된다.

Source

Github 전체소스