2468번 : 안전 영역

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

2468번: 안전 영역

 

 

문제

 

 

코드

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

public class Main {
    static int[][] g;
    static boolean visited[][];
    static int dx[] = {0,0,-1,1};
    static int dy[] = {-1, 1, 0, 0};
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());

        g = new int[n][n];
        for(int i=0;i<n;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j=0;j<n;j++) {
                g[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int count;
        int max = 0;
        for(int h=1;h<=100;h++) {
            count=0;
            visited = new boolean[n][n];
            for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++) {
                    if(g[i][j]>h && visited[i][j] == false) {
                        bfs(i,j,h); count++;
                    }
                }
            }
            if(max<count) max=count;
        }
        
        if(max==0) max = 1;
        bw.write(max + "");
        bw.flush();
    }

    public static void bfs(int i, int j, int h) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{i, j});
        visited[i][j] = true;
        
        while(!q.isEmpty()) {
            int node[] = q.poll();
            i = node[0];
            j = node[1];
            for (int k = 0; k < 4; k++) {
                int x = i + dx[k];
                int y = j + dy[k];
                if (x < 0 || y < 0 || x >= n || y >= n) continue;
                if (g[x][y] > h && visited[x][y] == false) {
                    visited[x][y] = true;
                    q.add(new int[]{x, y});
                }
            }
        }
    }
}

 

 

해결방법

안전 영역의 최대 개수를 구하기 위해 비의 양마다 입력받은 그래프에 bfs를 사용하였다. 

 

결과는 76%에서 "틀렸습니다."가 떴다.

이유는 문제에 "아무 지역도 물에 잠기지 않을 수도 있다."라는 조건이 있는데 이 말의 의미는 "비가 안 올 수도 있다."라는 의미도 있었다. 이유는 모든 지역의 높이가 1인 경우 모든 지역이 물에 잠기지 않으려면 비가 안 와야 하기 때문이다.

즉, 안전 영역의 개수는 1개 이상이다. 처음에 낸 코드는 안전 영역의 개수가 0개일 때 최소이기에 "틀렸습니다"가 뜬 것이다. 이를 해결하기 위해 max값이 0일 때 1을 출력하도록 하였다. 이 조건을 이해하지 못한 사람이 많기에 정답률이 저조한 것 같다.

 

2

1 1

1 1

output => 0

answer => 1

 

처음에 "입력받은 배열을 다른 배열에 복사하여 bfs 진행"을 반복하였는데 다른 사람의 풀이를 보니 굳이 복사하지 않고 "visited를 생성하여 bfs 진행" 하면 복사하지 않기에 코드도 짧아지고 더 성능이 좋아 코드를 수정하였다.