[백준 1743 /음식물 피하기 / JAVA / 완전 탐색]

 

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

1743번: 음식물 피하기

 

문제 접근

배열 공간에서 음식물 쓰레기를 발견하면 해당 위치를 기준으로 BFS, DFS 중 탐색 방법을 정한다.

DFS는 한 곳을 쭉 탐색했다가 처음 위치로 돌아오지만 BFS는 한 곳 탐색하고 다시 시작 위치로 와서 다음 방향을 탐색하기 때문에 움직일 방향을 Queue에 미리 저장해둔다.

 

++ 이런 문제에 익숙해질 필요가 있을 거 같다. 

 

DFS

import java.util.*;
import java.io.*;

public class Main {
	static int N, M, K, maxGarbageSize, garbageSize;
	static int dx[] = {-1, 1, 0, 0};
	static int dy[] = {0, 0, -1, 1};
	static boolean [][] map; // 맵 그리기
	static boolean [][] visit; // 방문 표시
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken()); // 세로
		M = Integer.parseInt(st.nextToken()); // 가로
		K = Integer.parseInt(st.nextToken()); // 음식물 갯수
		
		visit = new boolean[N+1][M+1];
		map = new boolean[N+1][M+1];
		
		for(int k=0; k<K; k++) { // 음쓰 위치 선정
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken()); // 음쓰 세로 좌표
			int c = Integer.parseInt(st.nextToken()); // 음쓰 가로 좌표
			map[r][c] = true;
		}
		
		for(int i=1; i<= N; i++) {
			for(int j=1; j<= M; j++) {
				if(visit[i][j] == false && map[i][j] ) { // 방문하지 않았으면서 쓰레기가 있는 공간이라면
					garbageSize = 0;
					dfs(i, j);
					maxGarbageSize = Math.max(maxGarbageSize, garbageSize);
				}
			}
		}
		System.out.println(maxGarbageSize);
		
	}
	
	public static void dfs(int x, int y) {
		garbageSize++; // 음쓰 발견 크기 +1
		visit[x][y] = true; // 방문했다 표시
		
		for(int i=0; i<4; i++) { // 위의 dy, dx 돌려서 네 방향 탐색, 0 : x 방향 -1 / 1 : x 방향 + 1 / 2 : y 방향 -1 / 3 : y 방향 + 1
			int plusX = x+dx[i];
			int plusY = y+dy[i];
			
			if(plusX < 1 || plusX > N || plusY < 1 || plusY > M ) continue; // 4방향 중 다음 움직일 칸이 map의 범위를 벗어나면
			if(visit[plusX][plusY] == false && map[plusX][plusY]) { // 4방향 중 다음 칸이 방문하지 않았고 음쓰가 있는 공간이라면
				dfs(plusX, plusY); // 재귀로 다시 타고 들어가서 끝까지 방문, 재귀 끝내고 돌아오면 반복문 i의 남은 인덱스 마저 다돌기
			}
			
		}
	}	
}

 

 

BFS

import java.util.*;
import java.io.*;

public class Main {
	static int N, M, K, maxGarbageSize, garbageSize;
	static int dx[] = {-1, 1, 0, 0};
	static int dy[] = {0, 0, -1, 1};
	static boolean[][] map;
	static boolean[][] visit;
	
	public static void main(String[] args) throws IOException {
	     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	     StringTokenizer st = new StringTokenizer(br.readLine());
	     
	     N = Integer.parseInt(st.nextToken());
	     M = Integer.parseInt(st.nextToken());
	     K = Integer.parseInt(st.nextToken());
	     
	     visit = new boolean[N+1][M+1];
	     map = new boolean[N+1][M+1];
	     
	     for(int k=0; k<K; k++) {
	    	 st = new StringTokenizer(br.readLine());
	    	 int r = Integer.parseInt(st.nextToken());
	    	 int c = Integer.parseInt(st.nextToken());
	    	 map[r][c] = true;
	     }
	     
	     for(int i=1; i<=N; i++) {
	    	 for(int j=1; j<=M; j++) {
	    		 if(visit[i][j] == false && map[i][j]) {
	    			 garbageSize = 0;
	    			 bfs(i,j);
	    			 maxGarbageSize = Math.max(maxGarbageSize, garbageSize);
	    		 }
	    	 }
	     }
		System.out.println(maxGarbageSize);
	}
	
	public static void bfs(int x, int y) {
		Queue<int[]> q = new LinkedList<>(); // 돌면서 발견한 음쓰 위치를 바로 탐색하기 위해 큐에 저장하기
		garbageSize++;
		
		q.add(new int[] {x,y});
		visit[x][y] = true;
		
		while(!q.isEmpty()) {
			int[] dir = q.poll();
			int qX = dir[0];
			int qY = dir[1];
			
			for(int i=0; i<4; i++) {
				int plusX = qX + dx[i];
				int plusY = qY + dy[i];
				if(plusX < 1 || plusX > N || plusY < 1 || plusY > M) continue;
					
				if(visit[plusX][plusY] == false && map[plusX][plusY]) {
					q.add(new int[] {plusX, plusY});
					visit[plusX][plusY] = true;
					garbageSize++;
				}
				
			}
		}
	}
}