OJ
[BOJ] 1743 음식물 피하기 (JAVA)
P3PP4
2022. 12. 11. 20:36
https://www.acmicpc.net/problem/1743
1743번: 음식물 피하기
첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다
www.acmicpc.net
기본적인 BFS 문제입니다.
음식물이 떨어진 곳을 1, 아닌 곳을 0으로 두고 2차원 배열 전체를 탐색하면서 음식물을 발견하면 BFS를 수행하여 최대 크기를 찾아냅니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
int[] dr = { -1, 0, 1, 0 };
int[] dc = { 0, 1, 0, -1 };
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[][] arr = new int[N][M];
boolean[][] visited = new boolean[N][M];
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;
arr[r][c] = 1;
} // end of input
Queue<int[]> q = new LinkedList<>();
int result = 0;
for (int row = 0; row < N; row++) {
for (int col = 0; col < M; col++) {
// 음식물 발견
if(arr[row][col] == 1 && !visited[row][col]) {
q.offer(new int[] { row, col });
visited[row][col] = true;
int cnt = 1;
while(!q.isEmpty()) {
int[] a = q.poll();
// 4방 탐색
for (int dir = 0; dir < 4; dir++) {
int nr = a[0] + dr[dir];
int nc = a[1] + dc[dir];
if(0 <= nr && nr < N && 0 <= nc && nc < M && !visited[nr][nc] && arr[nr][nc] == 1) {
cnt++;
q.offer(new int[] { nr, nc });
visited[nr][nc] = true;
}
}
}
result = Math.max(result, cnt);
}
}
}
System.out.print(result);
}
}