import java.awt.image.BufferStrategy; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.util.StringTokenizer; public class Main { static boolean [][] map; static boolean [][] visited; static boolean [][] discoveredLand; static int route; static int N; static BufferedReader br; static boolean endLoop; public static void main(String[] args) throws IOException { initialize(); Coordinate nextLand = getStartPoint(); try{ while(endLoop) { nextLand = findNextLand(nextLand); } } catch(NoNewLandException e) { System.out.println(route); } /* 임의의 첫 땅으로부터 BFS; 같은 영역을 1로 처리; 임의의 첫 땅 으로부터 다시 BFS -> 다음 땅 나올때까지 route 계산; 단, 같은 영역(반복문 감안하면, 이미 나온 땅은)끼리는 route++를 안함; 다음 땅 나오면 다시 앞의 행동 반복; break 조건: 새로운 땅이 안나오고 모든 주변이 visited면. */ } static Coordinate findNextLand(Coordinate initialPoint) throws NoNewLandException{ Queue landQueue = discoverLand(initialPoint); return BFSNextLand(landQueue); } static Queue discoverLand(Coordinate initialPoint) { Queue queue = new ArrayDeque<>(); Queue resultQueue = new ArrayDeque<>(); queue.add(initialPoint); resultQueue.add(initialPoint); discoveredLand[initialPoint.row][initialPoint.col] = true; while(!queue.isEmpty()) { Coordinate c = queue.remove(); for(Coordinate sur : c.getSurroundings()) { if(sur.row<0||sur.row>=N||sur.col<0||sur.col>=N) continue; if(discoveredLand[sur.row][sur.col]|| !map[sur.row][sur.col]) continue; discoveredLand[sur.row][sur.col] = true; queue.add(sur); resultQueue.add(sur); } } return resultQueue; } static Coordinate BFSNextLand(Queue initialLand) { Queue> queue = new ArrayDeque<>(); visited = new boolean[N][N]; for(Coordinate c : initialLand) { queue.add(new Pair<> (c,0)); visited[c.row][c.col] = true; } while(!queue.isEmpty()) { Pair pair = queue.remove(); for(Coordinate sur:pair.k.getSurroundings()) { if(sur.row<0||sur.row>=N||sur.col<0||sur.col>=N) continue; if(visited[sur.row][sur.col]) continue; visited[sur.row][sur.col] = true; queue.add(new Pair<> (sur,pair.v + 1)); if(map[sur.row][sur.col] && !discoveredLand[sur.row][sur.col]) { route = Math.min(route, pair.v); return sur; } } } throw new NoNewLandException(); } static Coordinate getStartPoint() { for(int i=0;i { K k; V v; Pair(K k, V v) { this.k = k; this.v = v; } }

제출 #105879

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: