반응형
https://www.acmicpc.net/problem/16197
알고리즘 종류
완전탐색
사고 과정
1. 코인1과 코인2를 담는 객체가 필요하다.
2. BFS를 활용하여 코인의 이동을 구현한다. 이때 재방문을 방지하기 위해서 isVisited[][][][]를 활용한다.
3. 각 코인이 범위 내에서 벽을 만났는지, 범위 내에서 이동했는지, 범위 밖으로 나갔는지 확인한다.
구현(C++)
|
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
|
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Vector;
public class Main {
static int n, m;
static char[][] mat;
static int[][][][] isVisited;
static Vector<tmp_coin> state;
static int[][] dir = {{1,0}, {0,1}, {-1,0}, {0,-1}};
public static class tmp_coin{
int y, x;
tmp_coin(int y, int x){
this.y = y;
this.x = x;
}
}
public static class coin{
int y1, x1, y2, x2;
coin(int y1, int x1, int y2, int x2){
this.y1 = y1;
this.x1 = x1;
this.y2 = y2;
this.x2 = x2;
}
}
public static boolean isValid(int y, int x) {
return (y>=0&&y<n) && (x>=0&&x<m);
}
public static void bfs() {
Queue<coin> q = new LinkedList<coin>();
q.add(new coin(state.get(0).y, state.get(0).x, state.get(1).y, state.get(1).x));
isVisited[state.get(0).y][state.get(0).x][state.get(1).y][state.get(1).x]=1;
int time=0;
while(!q.isEmpty()) {
time++;
if(time > 10) {
System.out.println(-1);
return;
}
int size = q.size();
for(int i=0; i<size; i++) {
coin c = q.remove();
for(int d=0; d<4; d++) {
int ny1 = c.y1 + dir[d][0];
int nx1 = c.x1 + dir[d][1];
int ny2 = c.y2 + dir[d][0];
int nx2 = c.x2 + dir[d][1];
boolean flag1 = false;
boolean flag2 = false;
// coin 1
if(isValid(ny1, nx1) && mat[ny1][nx1] == '#') {
ny1 = c.y1;
nx1 = c.x1;
}
else if(!isValid(ny1, nx1)) {
flag1 = true;
}
// coin 2
if(isValid(ny2, nx2) && mat[ny2][nx2] == '#') {
ny2 = c.y2;
nx2 = c.x2;
}
else if(!isValid(ny2, nx2)) {
flag2 = true;
}
if(flag1 && flag2) continue;
if(flag1 || flag2) {
System.out.println(time);
return;
}
if(isVisited[ny1][nx1][ny2][nx2]==1) continue;
q.add(new coin(ny1, nx1, ny2, nx2));
isVisited[ny1][nx1][ny2][nx2] = 1;
}
}
}
System.out.println(-1);
return;
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
mat = new char[n+1][m+1];
isVisited = new int[n+1][m+1][n+1][m+1];
state = new Vector<tmp_coin>();
for(int i=0; i<n; i++) {
String str = sc.next();
for(int j=0; j<m; j++) {
mat[i][j] = str.charAt(j);
if(mat[i][j] == 'o') {
state.add(new tmp_coin(i,j));
mat[i][j] = '.';
}
}
}
bfs();
}
}
|
cs |
시행착오
반응형
'코딩 공부 > 백준' 카테고리의 다른 글
| [백준][C++ ] 20058 마법사 상어와 파이어스톰 (0) | 2021.05.26 |
|---|---|
| [백준][C++] 20057 마법사 상어와 토네이도 (0) | 2021.05.25 |
| [백준][C++] 20056 마법사 상어와 파이어볼 (0) | 2021.05.25 |
| [백준][C++] 1107 리모컨 (0) | 2021.04.22 |
| [백준][C++] 1976 여행 가자 (0) | 2021.04.22 |