[백준-JAVA] 할로윈 묘지 3860번

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

 

 

🤔 풀기 전의 문제에 대한 생각

☑️ 문제를 읽으며

문제를 읽고 생각한 것은 좌표를 간선을 이용해서 연결하여 그래프로 만들자 였다.

BFS에서 4방향으로 이동하는 것을 간선을 통해서 표현하고

벨만 포드 알고리즘을 통해서

최단거리를 구하려 했다.

문제 자체도 계속해서 과거를 돌아가는 것을 출력하라고 하기에

대놓고 벨만 포드 문제라고 생각했다. 물론 해당 문제를 가지고 플로이드는 실행하지 못한다. N 이 900가 되기에 3제곱이 되면 시간복잡도가 무조건 터진다.

핵심

결국 이 문제의 핵심은 개인적으로 바라볼때 구현력이다.

좌표를 간선으로 연결해서 그래프로 만드냐

이 부분에서 나는 처음에 가로 → 이 방향과 세로 위 방향을 순회하면서

연결시켰지만 끝내 오류가 계속나고 구현이 제대로 안되서

포기하고 정석적인 BFS 방향으로 간선을 만들어갔다.

간선 연결 - 그래프 만들기

이 문제의 핵심은 3가지다.

1. 출구에 도착하면 바로 나간다.
2. 귀신구멍에 빠지면 해당 반대편으로 무조건 이동한다
3. 묘지로 갈 수없다.

이 3가지를 주의해서 구현하면 끝이다.

우리는 BFS 하는 방식으로 좌표 평면에서 움직이면서 간선을 이어줄 것이다.

여기서 내가 생각한 것은

4x3이라면 좌표평면의 각 칸을 (좌표를)

0 1 2 3

4 5 6 7

8 9 10 11

이런식으로 넘버링한것이다.

이렇게 넘버링하면 간선을 연결할때 편하게 생각이 가능하다.

해당 식은 해당 행 * W(너비) + 열을 하면 해당 번호가 나오게 된다.

이렇게 BFS를 돌리며 간선을 연결하는 데

BFS돌리는 시작 노드인지, 다음 즉 간선에 연결된 노드인지에 따라 조건이 결정된다.

1. 시작 지점 인 경우
   1. 묘지에서 시작안된다.
   2. 출구는 시작안하고 바로 나간다.
   3. 귀신구멍에서 나가는 유일한 길은 이미 하나로 정해져 있기에 시작으로 설정안한다.
2. 다음 지점 (간선에 연결된 부분)
   1. 묘지는 안된다.
   2. 출구는 다음 지점으로 가능
   3. 귀신구멍 역시 귀신구멍에서 나가는게 안되는 것이지 가는 것은 가능하다.

이 정도만 주의하면 끝이다.

🧶 예상 시간 복잡도

벨만 포드 알고리즘이기에 VE

✅ 코드

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

class Main{
	static class Edge {
		int src,dest;
		long cost;
		public Edge (int src,int dest,long cost) {
			this.src = src;
			this.dest = dest;
			this.cost = cost;
		}
		@Override
		public String toString() {
			return src+" "+dest+" "+cost;
		}
	}
	static int[] dx = {0,-1,0,1};
	static int[] dy = {1,0,-1,0};
	static int W,H;
	static ArrayList<Edge> adj;
	static long[] dist;
	static HashSet<Integer> ghost;
	static HashSet<Integer> hole; 
	public static void main (String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		while (true) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			if (W == 0 && H == 0) break;
			// 출구 노드 기록 
			int out = W*H -1;
			// 묘지 위치 기록 
			ghost = new HashSet<>();
			hole = new HashSet<>();
			adj = new ArrayList<>();
			int G = Integer.parseInt(br.readLine());
			
			for (int i = 0;  i< G;i++) {
				st = new StringTokenizer(br.readLine());
				int y = Integer.parseInt(st.nextToken());
				int x = Integer.parseInt(st.nextToken());
				
				int node = x*W + y;
				ghost.add(node);
			}
			// 귀신의 구멍 기록 
			int E = Integer.parseInt(br.readLine());
			for (int i= 0 ; i< E; i++) {
				st = new StringTokenizer(br.readLine());
				int y1 = Integer.parseInt(st.nextToken());
				int x1 = Integer.parseInt(st.nextToken());
				
				int from = x1*W + y1;
				int y2 = Integer.parseInt(st.nextToken());
				int x2 = Integer.parseInt(st.nextToken());
				int to = x2*W + y2;
				
				int c = Integer.parseInt(st.nextToken());
				hole.add(from);
				
				adj.add(new Edge(from,to,c));
			}
			// 간선 연결
			for (int x = 0 ; x < H; x++) {
				for (int y = 0; y < W; y++) {
					int node = x*W+y;
					// 시작이 묘비,귀신구멍, 출발지 일경우 건너띄기 
					if (ghost.contains(node) || hole.contains(node) || 
							out == node) continue;
					for (int dir = 0; dir < 4; dir ++) {
						int nx = x + dx[dir];
						int ny = y + dy[dir];
						if (nx <0 || ny <0|| nx >= H || ny >= W) continue;
						int next = nx*W + ny;
						// 다음이 묘비면 건너띄기 
						if (ghost.contains(next)) continue;
						
						adj.add(new Edge(node,next,1));
					}
				}
			}
			// 과거로 계속 돌아간다 -> 음의 사이클 
			if (!BFM(0)) {
				sb.append("Never\\n");
			}else {
				// 빠져나올수없다 -> 값이 MAX다
				if (dist[out] == Long.MAX_VALUE) sb.append("Impossible\\n");
				// 그 외 출력
				else sb.append(dist[out]+"\\n");	
			}
		}
		System.out.println(sb.toString());
	}
	private static boolean BFM(int st) {
		dist = new long[W*H];
		Arrays.fill(dist, Long.MAX_VALUE);
		dist[st] = 0;
		
		for (int i = 0 ; i < W*H - ghost.size() -1; i ++) {
			for (Edge edge : adj) {
				if (dist[edge.src] == Long.MAX_VALUE) continue;
				if (dist[edge.dest] > dist[edge.src] + edge.cost) {
					dist[edge.dest] = dist[edge.src] + edge.cost;
				}
			}
		}
		for (Edge edge : adj) {
			if (dist[edge.src] == Long.MAX_VALUE) continue;
			if (dist[edge.dest] > dist[edge.src] + edge.cost) {
				return false;
			}
		}
		
		return true;
	}

}