[BOJ] 1743. 음식물 피하기 (Java)

문제 링크 / level: Silver I

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

1743번: 음식물 피하기

 

 

내가 생각한 풀이

오래간만에 BFS 문제, 특히 flood fill 문제를 보게 되었다. 반가운 마음(?)에 어찌저찌 잘 풀기는 했는데 조금 헤맸던 부분이 있어서 BFS 대표 문제들을 풀어보기로 했다. 꾸준히 연습하면서 감을 잃지 말아야지!!😎

 

...라고 생각해도 어떤 문제가 좋은지를 몰라서 다른 사람들이 만들어둔 문제집(?)에서 문제를 골라서 풀어봤다.

▲ 이 문제집에 있는 첫 번째 문제부터 풀어보았다.😊

 

문제의 핵심 (출처: BOJ)

전형적인 flood fill 문제였다. 다만 배열의 원소들을 다 주는 것이 아니고 음식물이 있는 좌표값을 주는 것이 특징이랄까. (참고로 좌표값은 인덱스 번호보다 1씩 크다.)

그렇다고 해도 매우 간단하다. 처음에 배열의 모든 원소를 0으로 초기화하고, 좌표값에 해당하는 원소들의 값만 1로 업데이트해주고 bfs해주면 끝이니까!!

 

// 핵심 코드
for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
		if(food[i][j] == 1 && visited[i][j] == 0) {
			bfs(i,j);
			max = (Math.max(max, cnt)==max) ? max : cnt;
		}
	}
}
System.out.println(max);

food 배열의 원소가 1인 것 = 음식물이 있는 곳 && 그리고 방문한 적 없는 곳에 한해서 bfs를 실행해준다.

그래서 문제의 핵심은 뭐다??

이 문제의 결론은 bfs를 실행해서 가장 큰 음식물의 사이즈를 출력하라는 것이다. 따라서 나는 cnt라는 변수를 이용해서 이를 간단하게 해결했다. 방법은 bfs가 한 번 실행되고 큐가 다 비워져서 함수를 빠져나올 때마다 max와 값을 비교해서 더 큰 값을 max의 값으로 업데이트해주는 것이다. (참고로 max = Integer.MIN_VALUE로 초기화 되어 있다.)

 

문제에 따라서는 visited 배열의 원소값을 활용하기도 하지만, 이 문제에서는 오로지 가장 큰 음식물의 크기만 출력하면 되기 때문에 visited 배열을 방문하면 일괄적으로 1으로 업데이트 해줬다. 그리고 철저하게 cnt 변수만 활용해줬다. 값 비교와 출력할 때 편의를 위해 static으로 선언한 것은 덤!!^_^ 참 쉽죠?😉 마지막에 max에 저장된 값만 출력하면 끝!!!

야호! 한 번에 성공!!

 

▼아래 더보기를 누르면 코드 전체를 볼 수 있습니다.

[코드 보기]