[swea-D4] 4193. 수영대회 결승전 ( 완전 탐색 + 구현 )
# [swea-D4] 4193. 수영대회 결승전 ( 완전 탐색 + 구현 )
문제
예선전에서 승리한 삼성이는 결승전 까지 진출하게 되었다.
결승전인 만큼 수영장이 아닌 바다에서 진행되었다.
바다 전체를 사용 할 수 없기에 가로 N 세로 N만큼의 공간만 사용하여 진행하도록 하였다.
이 공간을 벗어나면 실격처리가 되므로 공간안에서 가장 빠른 길을 찾아야 한다.
이 공간에는 섬과 같은 지나갈 수 없는 장애물과, 주기적으로 사라졌다 나타나는 소용돌이 같은 장애물이 존재한다.
( 섬과 같은 장애물은 지도에서 1로 표시, 소용돌이 같은 장애물은 2로 표시 )
소용돌이는 생성되고 2초동안 유지되다가 1초동안 잠잠해진다.
예를들어, 0초에 생성된 소용돌이는 0초, 1초까지 유지되고 2초에 사라지게된다.
또한 3초, 4초에는 생성되고 5초에 사라진다.
(단 ,한번 통과한 소용돌이 위에서는 머물러 있을 수 있다 )
이런 바다에서 삼성이를 우승시키려면 어떤 경로로 보내야 될까?
똑똑한 여러분들은 한번에 그 경로를 찾을 수 있었다. 해당 경로로 수영을 했을때 삼성이는 몇초만에 골인 할 수 있을까?
1
2
3
4
5
6
7
8
5 //N
0 0 0 0 0
0 0 0 1 0
0 0 0 1 0
2 2 1 1 0
0 0 0 0 0
4 0 //시작점
2 0 //도착점
EX)
이 경우에는 (4,0) 에서 시작, 소용돌이가 존재하므로 이동하지 않는다 ( 0초 )
(4,0) 아직 소용돌이가 사라지지 않았으므로 제자리에 있다 ( 1초)
(4,0) 이제 소용돌이가 사라지는 것을 보았고 건너려고한다 ( 2초)
(3,0) 소용돌이를 통과하였고 바다위를 수영하고 있다 (3초)
(2,0) 도착지에 도착하였다 (4초)
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 수영장의 크기 N ( 2<=N<=15 )
다음 N개의 줄의 i번째 줄에는 수영장의 모양이 공백으로 구분되어 주어진다.
( 0 : 지나갈 수 있는 곳 , 1 : 장애물 , 2: 주기가 2초인 소용돌이)
다음으로 시작위치 A,B가 주어지고 ( 0<=A,B<=N-1)
마지막 줄에 도착위치 C, D가 주어진다
( 0 <=C,D<=N-1) ( 도착점과 시작점은 소용돌이가 아니다 )
출력
각 테스트 케이스마다 테스트 케이스의 번호와 이동시간을 공백을 두고 표시한다
도착 할 수 없다면 -1을 출력한다.
(Ex) #1 4
🙋♂️ 들어가며
문제를 읽어보니 2가지 동작이 필요하다.
- 이동
- 제자리 대기
우선순위는 이동이 1순위고, 제자리 대기가 2순위겠다
장애물을 정리하자
- 1 : 이동 불가
- 2 : 특정 시간마다 이동 가능
소용돌이 (0초 시작)
- 0, 1,
2 - 3, 4,
5 - 6, 7,
8
x % 3 을 쓰면 되겠다
그리고 조심할 것은 다음과 같다.
매 testcase마다 min_cost가 초기화 되도록 할 것.
min_cost 값에 변화가 없다면 -1 출력
입력
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
3
5
0 0 0 0 0
0 0 0 1 0
0 0 0 1 0
2 2 1 1 0
0 0 0 0 0
4 0
2 0
6
0 0 0 0 0 0
0 1 1 0 0 0
0 0 0 1 2 0
1 1 0 1 0 1
0 0 0 1 0 1
0 0 0 2 0 1
5 0
2 5
6
0 0 0 0 0 0
0 0 0 0 0 0
1 0 1 1 1 0
1 0 0 0 0 0
1 0 1 1 1 0
0 0 2 0 2 0
5 0
3 5
출력
1
2
3
#1 4
#2 10
#3 7
✅ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
// bfs
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
static int N;
static int sr, sc, er, ec;
static int min_time;
static int[][] arr;
static int[] dr = {-1,1,0,0};
static int[] dc = {0,0,-1,1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc < T+1; tc++) {
// 0. 최소값 초기화
min_time = Integer.MAX_VALUE;
// 1. 배열 생성
N = Integer.parseInt(br.readLine());
arr = new int[N][N];
for (int r = 0; r < N; r++) {
String[] cols = br.readLine().split(" ");
for (int c = 0; c < N; c++) {
arr[r][c] = Integer.parseInt(cols[c]);
}
}
// 2. 시직점, 끝점
String[] sr_sc = br.readLine().split(" ");
String[] er_ec = br.readLine().split(" ");
sr = Integer.parseInt(sr_sc[0]);
sc = Integer.parseInt(sr_sc[1]);
er = Integer.parseInt(er_ec[0]);
ec = Integer.parseInt(er_ec[1]);
// 3. bfs
bfs();
// 4. 출력
if (min_time == Integer.MAX_VALUE) {
System.out.println("#" + tc + " " + -1);
}
else {
System.out.println("#" + tc + " " + min_time);
}
}
}
// 5. bfs 함수
static void bfs() {
// 5-1. q, 방문배열 생성 후에, 초기값 삽입
Queue<int[]> q = new LinkedList<>();
boolean[][][] visited = new boolean[N][N][3];
int start_time = 0;
q.add(new int[] {sr, sc, start_time});
visited[sr][sc][start_time % 3] = true;
// 5-2. 검사
while (!q.isEmpty()) {
int[] cur_pos = q.poll();
int cr = cur_pos[0];
int cc = cur_pos[1];
int cur_time = cur_pos[2];
// !! 끝점 도달시 반환
if (cr == er && cc == ec) {
min_time = Math.min(min_time, cur_time);
return;
}
// 5-3. 다음 시간
int next_time = cur_time + 1;
// 5-4. 다음 방향
for (int d = 0; d < 4; d++) {
int nr = cr + dr[d];
int nc = cc + dc[d];
// 5-5. 범위 검사
if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
// 5-6. 장애물 검사
if (arr[nr][nc] == 1) continue;
// 5-7. 소용돌이 못지나가는 경우
if (arr[nr][nc] == 2 && cur_time % 3 != 2) continue;
// 5-8. 방문 했다면
if (visited[nr][nc][next_time % 3]) continue;
// 5-9. 방문 안했다면
visited[nr][nc][next_time % 3] = true;
q.add(new int[] {nr, nc, next_time});
}
// 6. 제자리에서 대기해야하는가?
if (!visited[cr][cc][next_time % 3]) {
visited[cr][cc][next_time % 3] = true;
q.add(new int[] {cr, cc, next_time});
}
}
}
}
