mingggggg

1. 문제

https://www.acmicpc.net/submit/1743/43040661

2. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int[][] list;
	static int answer;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		list = new int[M][N];

		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			list[Integer.parseInt(st.nextToken()) - 1][Integer.parseInt(st.nextToken()) - 1] = 1;
		}

		// 입력 종료 && 인접 리스트 입력 종료

		int result = 0;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (list[i][j] == 1) {
					result = Math.max(bfs(i, j, N, M, list), result);

				}
			}
		}

		System.out.println(result);

//		// 인접 리스트 출력
//		for (int i = 0; i < M; i++) {
//			for (int j = 0; j < N; j++) {
//				System.out.printf("%d ", list[i][j]);
//			}
//			System.out.println();
//		}
	}

	public static int bfs(int r, int c, int N, int M, int[][] list) {

		Queue<int[]> q = new LinkedList<>();

		q.add(new int[] { r, c });
		list[r][c] = 9;

		answer = 1;
		while (!q.isEmpty()) {

			int now[] = q.poll();

			for (int i = 0; i < 4; i++) {

				int nextX = now[0] + dx[i];
				int nextY = now[1] + dy[i];

				if (nextX < 0 || nextY < 0 || nextX >= M || nextY >= N) {
					continue;
				}

				if (list[nextX][nextY] != 1) {
					continue;
				}

				answer++;
				list[nextX][nextY] = 9;
				q.add(new int[] { nextX, nextY });
			}
		}
		return answer;
	}

}

3. 리뷰

전형적인 bfs 문제이다.

지금까지 인접 리스트로 문제를 풀어와서 인접 행렬로 변환해서 풀었다.

음식물이 있는 자리를 1로 변환하고 각 행렬을 탐색하면서 bfs를 수행했다.

정말 많이 푼 유형인데도 또 헤맸다... 연습만이 살 길인 것 같다.