링크 : https://www.acmicpc.net/problem/3860
문제 설명 :
오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아왔다.
상근이가 어렸을 적에 할머니는 상근이에게 할로윈 밤에 묘지에는 귀신 구멍이 나타난다고 말해주었다. 귀신 구멍으로 들어가면, 묘지의 다른 장소로 다시 나오게 된다. 이 구멍은 시간을 이동할 수 있는 구멍이다. 귀신 구멍에 떨어지면, 특정 시간이 지난 후(또는 이전)에 평행 우주의 다른 구멍에서 나오게 된다.
묘지는 W × H 크기의 그리드로 나타낼 수 있다. 묘지의 입구는 (0, 0)이고, 출구는 (W-1, H-1)이다. 상근이는 겁이 많기 때문에, 최대한 빨리 묘지를 나가려고 한다. 그리고 상근이는 이동하던 도중 출구에 도달하면 뒤도 돌아보지 않고 그 즉시 묘지를 빠져나갈 생각이다. 상근이는 현재 있는 칸과 동, 서, 남, 북으로 인접한 칸으로 이동할 수 있다. 각 칸은 잔디, 묘비, 또는 귀신 구멍이다.
- 묘비는 매우 높기 때문에, 묘비가 있는 칸으로는 이동할 수 없다.
- 귀신 구멍이 있는 칸으로 이동하면, 특정 시간이 지난 후에 묘지의 다른 곳에서 상근이가 나타나게 된다. 시간은 귀신 구멍마다 다르며, 양수, 음수, 0 중 하나이다.
- 잔디가 있는 칸으로는 자유롭게 이동할 수 있다.
상근이는 묘지를 빨리 나가기 위해 귀신 구멍도 이용할 것이다. 묘지를 나갈 수 없는 경우나, 계속해서 과거로 이동하는 경우가 존재할 수도 있다.
묘지가 위와 같이 생긴 경우(문제의 두 번째 예제)를 살펴보자. 묘비는 (2,1)와 (3,1)에 있고, 귀신 구멍은 0초만에 (3,0)로 들어가서 (2,2)에서 나오는 구멍 하나가 있다. 묘지를 빠져나오는데 걸리는 가장 빠른 시간은 4초이며, 다음과 같다.
(0,0) -> 동(1초) (1,0) -> 동(1초) (2,0) -> 동(1초) (3,0) -> 귀신구멍(0초) (2,2) -> 동(1초) (3,2)
귀신 구멍을 이용하지 않는다면 가장 빠른 시간은 5초이다.
입력 :
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 묘지의 너비 W와 높이 H가 주어진다. (1 ≤ W, H ≤ 30) 다음 줄에는 묘비의 개수 G (G ≥ 0)가 주어진다. 다음 G개 줄에는 묘비의 위치를 나타내는 두 정수 X와 Y가 주어진다. (0 ≤ X < W, 0 ≤ Y < H)
다음 줄에는 귀신 구멍의 수 E (E ≥ 0)가 주어진다. 다음 E개 줄에는 귀신 구멍의 정보를 나타내는 X1, Y1, X2, Y2, T 가 주어진다. (X1, Y1)은 귀신 구멍의 위치이고, (X2, Y2)는 그 귀신 구멍으로 들어갔을 때, 나오는 곳의 위치이다. (0 ≤ X1, X2 < W, 0 ≤ Y1, Y2 < H) (X1,Y1)과 (X2,Y2)가 같을 수도 있다. T는 귀신 구멍에서 나오는데 걸리는 시간이다. (-10,000 ≤ T ≤ 10,000) T가 양수인 경우에는 귀신 구멍을 들어간 이후에 나온다는 의미이다. 두 귀신 구멍이 같은 장소에 있거나, 구멍에서 나오는 지점이 묘비인 경우는 없다. 묘비와 귀신 구멍이 (0, 0)이나 (W-1, H-1)에 있는 경우는 없다.
입력의 마지막 줄에는 0 0이 주어진다.
출력 :
각 테스트 케이스 마다 상근이가 과거로 계속해서 돌아간다면 "Never"를 출력하고, 출구를 빠져나올 수 없으면 "Impossible"을 출력한다. 그 외의 경우에는 묘지를 빠져나오는데 가장 빠른 시간을 출력한다.
예제 입력 :
3 3
2
2 1
1 2
0
4 3
2
2 1
3 1
1
3 0 2 2 0
4 2
0
1
2 0 1 0 -3
0 0
예제 출력 :
Impossible
4
Never
접근법 :
1) 어떻게 풀 것인가?
음수 간선이 존재하는 2차원 지도에서 최단경로를 찾아가야한다.
2차원 지도의 경우에도 최단경로를 구하는 로직은 동일하다.
지도에서 1칸 이동하는 것을 cost : 1로 하고,
귀신 구멍에서 소비하는 시간을 cost : t로 하면 된다.
그림으로 설명하자면,아래 그림처럼 칸을 하나의 정점으로 보고,
이동 경로를 edge라고 생각하면 이해하기 쉽다.
묘비 개수에 따라 EdgeList 간선 리스트 개수가 달라질 수 있으므로,
ArrayList<Edge> edgeList로 선언을 해주고
최초 귀신구멍은 edgeList에 모두 더하고,
BFS를 통해 가능한 이동경로를 모두 edgeList에 추가로 더해주고
(이때, 묘비는 피해야하며, cost는 1로 넣어줌)
밸만-포드를 수행하면 된다.
기본 밸만 포드가 정점 개수 N, 간선 개수 M이라고 할때
N*M번 수행했는데, 이 경우에는 음수 싸이클을 확인하려면
N = (W*H) * 간선 개수 만큼 밸만 포드를 수행하면 된다.
기타 로직은 기본 밸만 포드 로직과 동일하다.
가능하면 밸만포드 기본 문제인 타임머신을 먼저 풀어보는 것을 추천.
https://subbak2.tistory.com/68
[BOJ 백준] 타임머신(11657) Java
링크 : https://www.acmicpc.net/problem/11657 문제 설명 : 더보기 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작
subbak2.tistory.com
주요 함수는 2개이다.
makePath( ); - 가능한 경로를 edgeList에 넣어주는 함수
static void makePath() {
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
// 묘비 or 귀신구멍이거나 도착지이면 continue
if (map[i][j] != 0 || (i == H - 1 && j == W - 1)) continue;
for (int k = 0; k<=3; k++) {
int nr = i + dr[k];
int nc = j + dc[k];
if ( nr >=0 && nr <H && nc >= 0 && nc < W && map[nr][nc] >=0 ) {
edgeList.add(new Edge(new Point(i,j), new Point(nr, nc), 1));
}
}
}
}
}
2차원 밸만포드 함수
static void BellmanFord() {
// dist INF로 초기화
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
dist[i][j] = INF;
}
}
// 출발점은 0으로
dist[0][0] = 0;
// 1. N - 1번 동안 간선 M을 모두 확인하기
for (int i = 0; i < W * H; i++) {
int len = edgeList.size();
for (int j = 0; j < len; j++) {
Edge now = edgeList.get(j);
Point start = now.start;
Point end = now.end;
// 1-1. 귀신구멍 출발지가 현재 무한대이면 continue
if (dist[start.y][start.x] == INF)
continue;
// 1-2. 최솟값으로 값 갱신 가능하면 갱신
dist[end.y][end.x] = Math.min(dist[end.y][end.x], dist[start.y][start.x] + now.cost);
}
}
// 2. 마지막으로 간선 M을 모두 확인해서 갱신이 발생하면 무한루프
int len = edgeList.size();
for (int j = 0; j < len; j++) {
Edge now = edgeList.get(j);
Point start = now.start;
Point end = now.end;
// 2-1. 귀신구멍 출발지가 현재 무한대이면 continue
if (dist[start.y][start.x] == INF)
continue;
// 갱신이 발생한다면 무한루프에 빠질 수 있음
if (dist[start.y][start.x] + now.cost < dist[end.y][end.x]) {
infFlag = true;
return;
}
}
}
2) 시간복잡도
시간 복잡도가 O(N^4)이나 N이 30으로 작은편이어서 양호
(Java 기준 - 836ms)
3) 공간복잡도
N, M 모두 크지 않으므로 고려하지 않음.
4) 풀면서 놓쳤던점
특별히 없음.
5) 이 문제를 통해 얻어갈 것
벨만-포드를 2차원으로 어떻게 활용할 것인가
Java 코드 :
import java.io.*;
import java.util.*;
// 3860 할로윈 묘지
public class Main {
static class Edge {
Point start, end;
int cost;
public Edge(Point start, Point end, int cost) {
this.start = start;
this.end = end;
this.cost = cost;
}
}
static class Point {
int y, x;
public Point(int y, int x) {
this.y = y;
this.x = x;
}
}
static int W, H, G, E; // W : 맵의 가로 H : 세로 G : 묘비의 개수 E : 귀신 구멍 수
static int[][] map; // -1 : 묘비 1 : 귀신구멍
static long[][] dist;
static ArrayList<Edge> edgeList;
static boolean infFlag;
// 좌표이동용 변수
static final int[] dr = { -1, 1, 0, 0 };
static final int[] dc = { 0, 0, -1, 1 };
static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder(); // 정답 출력용
for (;;) {
// 1. 입력 & 초기화
StringTokenizer st;
st = new StringTokenizer(br.readLine());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
// 0-0 이 입력되면 종료
if (W == 0 && H == 0)
break;
map = new int[H][W];
dist = new long[H][W];
infFlag = false;
// 묘비 입력
G = Integer.parseInt(br.readLine());
int x, y;
for (int i = 1; i <= G; i++) {
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
// 묘비는 못 가는 곳이므로 map에 -1 표시
map[y][x] = -1;
}
// 귀신구멍 입력
E = Integer.parseInt(br.readLine());
edgeList = new ArrayList<Edge>();
int x1, y1, x2, y2, t;
for (int i = 1; i <= E; i++) {
st = new StringTokenizer(br.readLine());
x1 = Integer.parseInt(st.nextToken());
y1 = Integer.parseInt(st.nextToken());
x2 = Integer.parseInt(st.nextToken());
y2 = Integer.parseInt(st.nextToken());
t = Integer.parseInt(st.nextToken());
// 귀신구멍에 1 표시
map[y1][x1] = 1;
// 간선리스트에 Edge 추가
edgeList.add(new Edge(new Point(y1, x1), new Point(y2, x2), t));
}
// 2. BFS로 가능한 모든 경로를 edgeList에 추가하기
makePath();
// 3. 밸만 포드
// ** dist는 출발지 1 제외하고 모두 무한대로
BellmanFord();
// 4. 출력
// 4-1. 무한루프가 가능하면 -1 출력
if (infFlag) {
sb.append("Never\n");
}
// 4-2. 무한루프 없으면 모든 도시의 최솟값 출력
else {
if (dist[H - 1][W - 1] == INF) {
sb.append("Impossible\n");
} else {
sb.append(dist[H - 1][W - 1] + "\n");
}
}
}
bw.write(sb.toString());
bw.flush();
bw.close();
br.close();
}
static void makePath() {
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
// 묘비 or 귀신구멍이거나 도착지이면 continue
if (map[i][j] != 0 || (i == H - 1 && j == W - 1)) continue;
for (int k = 0; k<=3; k++) {
int nr = i + dr[k];
int nc = j + dc[k];
if ( nr >=0 && nr <H && nc >= 0 && nc < W && map[nr][nc] >=0 ) {
edgeList.add(new Edge(new Point(i,j), new Point(nr, nc), 1));
}
}
}
}
}
static void BellmanFord() {
// dist INF로 초기화
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
dist[i][j] = INF;
}
}
// 출발점은 0으로
dist[0][0] = 0;
// 1. N - 1번 동안 간선 M을 모두 확인하기
for (int i = 0; i < W * H; i++) {
int len = edgeList.size();
for (int j = 0; j < len; j++) {
Edge now = edgeList.get(j);
Point start = now.start;
Point end = now.end;
// 1-1. 귀신구멍 출발지가 현재 무한대이면 continue
if (dist[start.y][start.x] == INF)
continue;
// 1-2. 최솟값으로 값 갱신 가능하면 갱신
dist[end.y][end.x] = Math.min(dist[end.y][end.x], dist[start.y][start.x] + now.cost);
}
}
// 2. 마지막으로 간선 M을 모두 확인해서 갱신이 발생하면 무한루프
int len = edgeList.size();
for (int j = 0; j < len; j++) {
Edge now = edgeList.get(j);
Point start = now.start;
Point end = now.end;
// 2-1. 귀신구멍 출발지가 현재 무한대이면 continue
if (dist[start.y][start.x] == INF)
continue;
// 갱신이 발생한다면 무한루프에 빠질 수 있음
if (dist[start.y][start.x] + now.cost < dist[end.y][end.x]) {
infFlag = true;
return;
}
}
}
}'알고리즘 Algorithm > BOJ 백준 (초급~중급)' 카테고리의 다른 글
| [BOJ 백준] 전구 (2449) Java (0) | 2021.07.28 |
|---|---|
| [BOJ 백준] 가장 큰 정사각형 (1915) Java (0) | 2021.07.28 |
| [BOJ 백준] 타임머신(11657) Java (0) | 2021.07.28 |
| [BOJ 백준] 거의 최단 경로(5719) Java (0) | 2021.07.28 |
| [BOJ 백준] 계단 오르기(2579) Java (0) | 2021.07.27 |
