백준 | 1743번. 음식물 피하기 - DFS & BFS 문풀

⬛ 백준 1743번. 음식물 피하기 - DFS & BFS 문풀

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

1743번: 음식물 피하기

문제

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

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

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

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

입력

첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다.  그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.

출력

첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.

---

💚나의 풀이 

풀이 - BFS 풀이

• 덩어리 개수를 구하는 게 아니라, 각 덩어리의 넓이가 가장 큰 크기를 구하는 문제이다.
• BFS로 인접 정점 우선으로 탐색을 하되, poll한 시점에서 넓이를 ++ 처리해야 제대로 카운팅이 된다는 것을 주의하자.

package to_0905_D;

import java.util.*;

/*1743번. 음식물 피하기 - DFS &BFS*/
public class Main {	
	static int N, M, K;
	static int[][] map;
	static boolean[][] visited;
	
	//4방향 
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	
	//BFS
	static int BFS(int x, int y) {
		Queue<int[]> Q = new LinkedList<>();
		int cnt = 0; //시작할 때 1로 세팅해서 
		visited[x][y] = true;
		Q.offer(new int[] {x, y});
		
		while(!Q.isEmpty()) {
			int[] cur = Q.poll();
			cnt++;
			for(int k=0; k<4; k++) {
				int nx = cur[0] + dx[k];
				int ny = cur[1] + dy[k];
				if(nx <0 || ny <0 || nx >=N || ny>=M ) continue;
				
				if(!visited[nx][ny] && map[nx][ny] == 1) {//1이 나타나면 
					Q.offer(new int[] {nx, ny});
					visited[nx][ny] = true;
				}
			}
		}
		return cnt;
	}
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		K = kb.nextInt();
		
		map = new int[N][M];
		visited= new boolean[N][M];
		
		for(int i=0; i<K; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			map[a-1][b-1] =1;
		}
	
		int max = Integer.MIN_VALUE;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 1) {
					max = Math.max(max, BFS(i, j));
				}
			}
		}
		System.out.println(max);
	}
}

---

풀이 - DFS 풀이

• 이번에는 재귀 호출로 넓이를 측정할 것이다.
• count 변수를 static으로 선언해놓고, main에서 새롭게 호출하는 출발점에서만 0으로 초기화한다.
• DFS가 호출되면 그 시작점에서부터 깊이 탐색을 하며 재귀가 반복 호출될 때마다 cnt++ 처리가 되도록 한다.
• 그 결과값이 최대인 것을 골라서 출력하면 정답이 된다.

import java.util.Scanner;

/*1743번. 음식물 피하기 - DFS &BFS*/
public class Main {	
	static int N, M, K;
	static int[][] map;
	static boolean[][] visited;
	static int count;
	
	//4방향 
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	//DFS
	static void DFS(int x, int y) {
		count++;//재귀 호출될 때마다  +1 처리
		visited[x][y] = true;
		
		for(int k=0; k<4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if(nx <0 || ny <0 || nx >= N || ny>= M) continue;
			if(!visited[nx][ny] && map[nx][ny] == 1) {
				DFS(nx, ny);//더 깊이 탐색하면서 나아감 
			}
		}
		
	}

	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		M = kb.nextInt();
		K = kb.nextInt();
		
		map = new int[N][M];
		visited= new boolean[N][M];
		
		for(int i=0; i<K; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			map[a-1][b-1] =1;
		}
	
		int max = Integer.MIN_VALUE;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(map[i][j] == 1) {
					count = 0;//여기서 0으로 초기화 해두고 
					DFS(i, j); //시작하지
					max = Math.max(max, count);
				}
			}
		}
		System.out.println(max);
	}
}