[백준 3860] 할로윈 묘지 (자바)

 

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

3860번: 할로윈 묘지

난이도 : 플레 5

 

벨만-포드를 이용했습니다. 입구, 귀신 구멍의 입, 출구 등 각 포인트를 기준으로 적절히 경로를 구했는데 시간 초과를 받았습니다. 모든 좌표가 포인트인 경우를 고려하지 못한 풀이였습니다.

 

그래서 각 좌표에서 이동할 수 있는 경우의 수를 경로로 만들고 벨만-포드를 돌리니 성공했습니다.

---

전역 변수

int w, h = 맵의 크기

int map[][] = 맵의 상태를 저장할 배열

long dist[][] = 벨만-포드에서 최단 경로를 저장할 배열

int dx[], dy[] = 경로 생성 시 이동 좌표

LinkedList<Edge> list = 경로

함수

void main

입력을 받습니다. 묘비의 위치는 map에서 -1로 표시되고 귀신 구멍의 입구는 1로 표시됩니다.

귀신 구멍의 입구에서 경로는 귀신 구멍의 출구로 바로 연결됩니다.

map을 이용하여 경로를 생성합니다. 그 후 벨만-포드를 실행하는데 음의 사이클이 있다면 "Never", 음의 사이클이 없지만, 목적지에 도착할 수 없는 경우에는 "Impossible" 그 외에는 값을 출력합니다.

(searchPath, bellmanFord 호출)

 

void searchPath

map을 돌면서 경로를 생성합니다. 목적지이거나 묘비, 귀신 구멍 입구인 경우에는 경로를 생성하지 않습니다.

(check 호출)

 

boolean check

현재 좌표가 유효한 값인지 확인합니다.

 

boolean bellmanFord

(0, 0)부터 벨만-포드를 시작합니다. 

2020/11/27 - [문제풀이/자바] - [백준 1865] 웜홀 (자바)

[백준 1865] 웜홀 (자바)

자세한 설명은 게시물로 대체합니다.

 

class Point

x, y 좌표를 나타내는 클래스입니다.

 

class Edge

시작 좌표와 끝 좌표, 경로 비용을 저장합니다.

좌표는 Point형이고 비용은 int형입니다.