글 읽기 - 3197 백조의호수 어느부분이 틀렸는지 잘 모르겠습니다.

lolgosu 3년 전 0

정말 오래 고민해봤는데, 어느 부분에서 틀렸는지 잘 모르겠습니다 ㅠ

Priority Queue를 사용해서, 라운드별로 탐색하는 범위를 한정지어 추가분 만큼만 수행할 수 있도록 했습니다.

같은 로직으로 백조간의 연결 여부와 물 범위의 확장을 따로따로 수행했고, 물 범위를 확장할 경우 Priority Queue의 남은 원소가 녹아야 할 얼음 지점이므로 물로 바꾸어 주었습니다.

무엇이 문제일까요?ㅜㅜ

import java.util.*;

public class Main {
	static int R, C, ey, ex, map[][], chk, rnd, dy[] = {0, 0, 1, -1}, dx[] = {1, -1, 0, 0};
	static boolean visitedL[][], visited[][];
	static PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
		@Override
		public int compare(int[] o1, int[] o2) {
			return Integer.compare(o1[2], o2[2]);
		}
	});
	static PriorityQueue<int[]> pq2 = new PriorityQueue<>(new Comparator<int[]>() {
		@Override
		public int compare(int[] o1, int[] o2) {
			return Integer.compare(o1[2], o2[2]);
		}
	});
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		R = sc.nextInt(); C = sc.nextInt();	map = new int[R][C]; visitedL = new boolean[R][C]; visited = new boolean[R][C];
		for(int i=0;i<R;i++) {
			String str = sc.next();
			for(int j=0;j<C;j++) {
				char cur = str.charAt(j);
				if(cur == '.') {
					map[i][j] = 0;
					pq2.add(new int[] {i, j, 0});
				}
				else if(cur == 'X') map[i][j] = 1;
				else {
					map[i][j] = 0;
					if(chk++ == 0) {pq.add(new int[] {i, j, 0}); pq2.add(new int[] {i, j, 0});}
					else {ey = i; ex = j;}
				}
			}
		}
		
		while(true) {
			if(isLinked()) break;
			searchExpand();
			expand();
			rnd++;
		}
		System.out.println(rnd);
	}
	
	static boolean isLinked() {
		while(!pq.isEmpty()) {
			int y = pq.peek()[0], x = pq.peek()[1], pri = pq.peek()[2];
			if(y == ey && x == ex) return true;
			if(pri == rnd + 1) return false;
			pq.poll();
			
			for(int i=0;i<4;i++) {
				int ny = y + dy[i], nx = x + dx[i];
				if(ny < 0 || ny >= R || nx < 0 || nx >= C || visitedL[ny][nx]) continue;
				if(map[ny][nx] == 1) pq.add(new int[] {ny, nx, pri + 1});
				else pq.add(new int[] {ny, nx, pri});
				visitedL[ny][nx] = true;
			}
		}
		return false;
	}
	
	static void searchExpand() {
		while(!pq2.isEmpty()) {
			int y = pq2.peek()[0], x = pq2.peek()[1], pri = pq2.peek()[2];
			if(pri == rnd + 1) return;
			pq2.poll();
			
			for(int i=0;i<4;i++) {
				int ny = y + dy[i], nx = x + dx[i];
				if(ny < 0 || ny >= R || nx < 0 || nx >= C || visited[ny][nx]) continue;
				if(map[ny][nx] == 1) pq2.add(new int[] {ny, nx, pri + 1});
				else pq2.add(new int[] {ny, nx, pri});
				visited[ny][nx] = true;
			}
		}
		return;
	}
	
	static void expand() {
		Iterator<int[]> iter = pq2.iterator();
		while(iter.hasNext()) {
			int[] cur = iter.next();
			map[cur[0]][cur[1]] = 0;
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

3197 백조의호수 어느부분이 틀렸는지 잘 모르겠습니다.

lolgosu 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말