[백준] 1743 음식물 피하기 - BFS(너비우선탐색) JAVA

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

코드설명

BFS(너비우선탐색)를 활용합니다.

 

구현 중에 유의해야할점은,

1. 해당 위치가 '#'일떄만 BFS가 작동하게합니다. 처음에는 단순히 visited[i][j]로 처리했는데 그럴경우 '#'이 아닌데도 호출되어 잘못하면 쓰레기칸과 인접한 칸이 호출되어 쓰레기칸으로 포함되어 Count되는 문제가 생깁니다. 그렇게 되면 최대 쓰레기양에 문제가 되겠지요.

for(int i=0;i<N; i++) {
    for(int j=0;j<M; j++) {
        if(visited[i][j] == false && matrix[i][j] == '#') {
            answer = Math.max(answer, BFS(i, j));
        }
    }
}

 

2. BFS에 필요한 데이터들 초기화시 cnt = 1 로 시작해야합니다. 이유는 해당 큐에 이미 데이터를 넣고 시작하기 때문에 다른 칸에서는 해당 칸에 도달하지 못합니다. 그러므로 cnt = 1 로 해야만 1개가 누락되지 않습니다.

static int BFS(int sr, int sc) {
    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[] {sr, sc});
    visited[sr][sc] = true;
    int cnt = 1;

 

코드

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D;
	static int answer = 0;
	static boolean[][] visited = new boolean[101][101];
	static int[] dx=  {-1,1,0,0};
	static int[] dy = {0, 0, -1, 1};
	static char[][] matrix = new char[101][101];
	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());
		
		for(int i=0;i<101; i++) {
			Arrays.fill(matrix[i], '.');
		}
		for(int i=0;i<K; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken()) - 1;
			int c = Integer.parseInt(st.nextToken()) - 1;
			matrix[r][c] = '#';
		}
		
		for(int i=0;i<N; i++) {
			for(int j=0;j<M; j++) {
				if(visited[i][j] == false && matrix[i][j] == '#') {
//					System.out.println("i, j"+i+" "+j);
					answer = Math.max(answer, BFS(i, j));
				}
			}
		}
		
		System.out.println(answer);
		
	}
	static int BFS(int sr, int sc) {
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {sr, sc});
		visited[sr][sc] = true;
		int cnt = 1;
		while(!q.isEmpty()) {
			int[] temp = q.poll();
			
			for(int dir = 0; dir < 4; dir++) {
				int nr = temp[0] + dx[dir];
				int nc = temp[1] + dy[dir];
				
				if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
				if(visited[nr][nc] == true) continue;
				if(matrix[nr][nc] == '.') continue;
				visited[nr][nc] = true;
				q.offer(new int[] { nr, nc});
				cnt += 1;
			}
		}
		
		return cnt;
	}
}