mingssssss

1. 문제

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

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 answer;
	static int[][] map;
	static int[][] check_map;
	static boolean[][] visited;
	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 N = Integer.parseInt(st.nextToken());

		map = new int[N][N];
		check_map = new int[N][N];

		int max = 0;
		int answer = 0;

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				max = map[i][j] > max ? map[i][j] : max; // 최댓값을 구해서 최댓값만큼 돌립니다.
			}
		}
		// 입력 종료
        
        // 모든 지역이 침수가 되면(배열의 최댓값) 그 이상 돌릴 필요가 없음
		for (int k = 0; k < max + 1; k++) {
            // 강우량 1부터 최댓값까지 탐색
			visited = new boolean[N][N];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j] <= k) {
						check_map[i][j] = 1; // 침수된 지역은 1로 표시(침수가 안 된 지역은 0)
					}
				}
			}
			int temp = 0;

			for (int r = 0; r < N; r++) {
				for (int c = 0; c < N; c++) {
					if (visited[r][c] == false && check_map[r][c] == 0) {
						BFS(r, c, k, N, check_map);
						temp++;
					}
				}
			}
			answer = answer < temp ? temp : answer;
			
		}
		
		System.out.println(answer);

//		// 출력
//		for (int i = 0; i < N; i++) {
//			for (int j = 0; j < N; j++) {
//				System.out.printf("%d ", map[i][j]);
//			}
//			System.out.println();
//		}
//
//		System.out.println(max);

	}

	public static void BFS (int r, int c, int k, int N, int[][] check_map) {
		
		// check_map 출력
//		System.out.println("**********");
//		for (int i = 0; i < N; i++) {
//			for (int j = 0; j < N; j++) {
//				System.out.printf("%d ", check_map[i][j]);
//			}
//			System.out.println();
//		}
		
		Queue<int[]> q = new LinkedList<>();
		visited[r][c] = true;
		q.add(new int[] {r, c});
		
		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 >= N || nextY >= N) {
					continue;
				}
				
				if (visited[nextX][nextY] == true || check_map[nextX][nextY] == 1) {
					continue;
				}
				
				visited[nextX][nextY] = true;
				q.add(new int[] {nextX, nextY});
				
				
			}
		}
		
		
	}

}

3. 리뷰

전형적인 bfs 문제인 것 같다. 이런 문제는 메모리와 시간 효율성을 고려해야 하는데

그 부분에서 조금 미흡한 것 같다.

주어진 지역을 map으로 받고, 동일한 크기의 배열(check_map)을 하나 더 만들어서

k를 0부터 돌려서 해당 맵에 침수된 지역이 있다면 그 좌표값을 1로 바꿨다.

바꾼 좌푯값에서 방문하지 않고 0인 지역의 좌푯값을 BFS에 넣고 돌렸다.

또한 map을 받아오면서 최댓값이 뭔지 확인했다. for문을 1부터(사실 0부터) 100까지

N의 범위 전체를 돌릴 필요가 없기 때문에, 최댓값을 구하면 그 이후로는

모든 지역이 침수되므로 탐색할 필요가 없다.

처음에는 비가 내리는 경우를 1부터 시작했는데(N의 범위가 1 ~ 100)이여서

노트에도 나와있지만 사실 비가 내리지 않는 경우도 고려해야 했다.

문제를 조금 더 꼼꼼히 읽는 습관을 들이고 bfs가 익숙해지도록 더 공부해야겠다.

그리고 최댓값을 구하는 방법인 Max를 사용하는 방법을 고려해봐야 겠다.