알고리즘
SWEA ::[모의 SW 역량테스트] 탈주범 검거
KorShaw
2021. 5. 2. 20:17
728x90
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
잡기 귀찮았다 ..
그냥 주어진 터널을 다 만들었다 ... 시뮬이라 특별한 알고리즘이나 자료구조는 없는듯하다.
탐색은 bfs로 했다. 역시 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
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
import java.util.*;
public class Solution_모의SW역량테스트_탈주범검거 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int tc=1; tc<=T; tc++) {
int n = sc.nextInt();
int m = sc.nextInt();
int start_x = sc.nextInt();
int start_y = sc.nextInt();
int l = sc.nextInt();
Queue<int[]> q = new LinkedList<int[]>();
boolean[][] visit = new boolean[n][m];
q.add(new int[] {start_x,start_y,1});
//상하좌우 주어진 터널 종류
int[][] tunnel_di = {{},{-1,1,0,0},{-1,1,0,0},{0,0,0,0},{-1,0,0,0},{0,1,0,0},{0,1,0,0},{-1,0,0,0}};
int[][] tunnel_dj = {{},{0,0,-1,1},{0,0,0,0},{0,0,-1,1},{0,0,0,1},{0,0,0,1},{0,0,-1,0},{0,0,-1,0}};
int[][] map = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
map[i][j] = sc.nextInt();
}
}
//돌면서 터널이 연결되는지 확인해야함 .. ㅠㅠ
while(!q.isEmpty()) {
int[] temp = q.remove();
int x = temp[0];
int y = temp[1];
int cnt = temp[2];
if(cnt > l) break;
visit[x][y] = true;
int tunnel_type = map[x][y];// 몇 번 터널이 있는지 확인하자
for (int i = 0; i < 4; i++) {
int nx = x + tunnel_di[tunnel_type][i];
int ny = y + tunnel_dj[tunnel_type][i];
if(nx >=0 && ny >= 0 && nx < n && ny < m && map[nx][ny]!=0 && !visit[nx][ny]) {
if(map[x][y] == 2 && i == 0 // 2번 파이프 위로 올라갈 수 있냐 ?
&& (map[nx][ny]==1||map[nx][ny]==2||map[nx][ny]==5||map[nx][ny]==6)) {
cnt++;
q.add(new int[] {nx,ny,cnt});
cnt--;
}else if(map[x][y] == 2 && i == 1 // 2번 파이프 아래로 갈 수 있냐 ?
&& (map[nx][ny]==2||map[nx][ny]==1||map[nx][ny]==4||map[nx][ny]==7)) {
cnt++;
q.add(new int[] {nx,ny,cnt});
cnt--;
}
if(map[x][y] == 3 && i == 2 // 3번 파이프 좌 방향
&& (map[nx][ny]==1||map[nx][ny]==3||map[nx][ny]==4||map[nx][ny]==5)) {
cnt++;
q.add(new int[] {nx,ny,cnt});
cnt--;
}else if(map[x][y] == 3 && i == 3 // 3번 파이프 우 방향
&& (map[nx][ny]==1||map[nx][ny]==3||map[nx][ny]==6||map[nx][ny]==7)){
cnt++;
q.add(new int[] {nx,ny,cnt});
cnt--;
}
if(map[x][y] == 4 && i==0 // 4번 파이프 위 방향
&& (map[nx][ny]==1||map[nx][ny]==2||map[nx][ny]==5||map[nx][ny]==6)) {
cnt++;
q.add(new int[] {nx,ny,cnt});
cnt--;
}else if(map[x][y] == 4 && i==3 // 4번 파이프 우
&& (map[nx][ny]==1||map[nx][ny]==3||map[nx][ny]==6||map[nx][ny]==7)) {
cnt++;
q.add(new int[] {nx,ny,cnt});
cnt--;
}
if(map[x][y] == 5 && i == 1// 5번 파이프 하
&& (map[nx][ny]==2||map[nx][ny]==1||map[nx][ny]==4||map[nx][ny]==7)) {
cnt++;
q.add(new int[] {nx,ny,cnt});
cnt--;
}else if(map[x][y] == 5 && i == 3// 5번 파이프 우
&& (map[nx][ny]==1||map[nx][ny]==3||map[nx][ny]==6||map[nx][ny]==7)) {
cnt++;
q.add(new int[] {nx,ny,cnt});
cnt--;
}
if(map[x][y] == 6 && i == 1// 6번 파이프 하
&& (map[nx][ny]==1||map[nx][ny]==2||map[nx][ny]==4||map[nx][ny]==7)) {
cnt++;
q.add(new int[] {nx,ny,cnt});
cnt--;
}else if(map[x][y] == 6 && i == 2// 6번 파이프 좌
&& (map[nx][ny]==1||map[nx][ny]==3||map[nx][ny]==4||map[nx][ny]==5)) {
cnt++;
q.add(new int[] {nx,ny,cnt});
cnt--;
}
if(map[x][y] == 7 && i==0
&&(map[nx][ny]==1||map[nx][ny]==2||map[nx][ny]==5||map[nx][ny]==6)) {
cnt++;
q.add(new int[] {nx,ny,cnt});
cnt--;
}else if(map[x][y] == 7 && i==2
&&(map[nx][ny]==1||map[nx][ny]==3||map[nx][ny]==4||map[nx][ny]==5)) {
cnt++;
q.add(new int[] {nx,ny,cnt});
cnt--;
}
if(map[x][y] == 1&& i==0
&& (map[nx][ny]==1||map[nx][ny]==2||map[nx][ny]==5||map[nx][ny]==6)) {
cnt++;
q.add(new int[] {nx,ny,cnt});
cnt--;
}else if(map[x][y] == 1&& i==1
&& (map[nx][ny]==2||map[nx][ny]==1||map[nx][ny]==4||map[nx][ny]==7)) {
cnt++;
q.add(new int[] {nx,ny,cnt});
cnt--;
}else if(map[x][y] == 1&& i==2
&& (map[nx][ny]==1||map[nx][ny]==3||map[nx][ny]==4||map[nx][ny]==5)) {
cnt++;
q.add(new int[] {nx,ny,cnt});
cnt--;
}else if(map[x][y] == 1&& i==3
&& (map[nx][ny]==1||map[nx][ny]==3||map[nx][ny]==6||map[nx][ny]==7)) {
cnt++;
q.add(new int[] {nx,ny,cnt});
cnt--;
}
}
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(visit[i][j])ans++;
}
}
System.out.println("#"+tc+" "+ ans);
}//tc끝
}
}
|
cs |
728x90