반응형
DFS를 이용하여 풀수 있는 문제이다.
일단 문제에서 10번이하로 움직인다는 조건을 주었다. 조건을 가지고 생각해보았을때 현재 구슬을 굴릴수 있는 방향은 4방향이 있고 10번을 굴린다 생각하면 전체가지수는 4^10이 나오게 된다. 4^10은 1,048,576 로써 충분히 완전탐색을 할수 있는 시간이 나온다. 하지만 좀더 최적화가 가능하기에 생각을 해보았다. 맨처음 구슬을 굴릴땐 4방향 다 굴릴수 있지만 그다음부턴 2방향으로만 굴릴수있다. 예를 들어 맨처음 위쪽으로 굴렸다 가정해보자면, 구슬은 벽을 맞닿을때까지 구르기 때문에 다음번엔 위쪽으로 굴리는 것은 무의미한 경우를 가지게 된다. 또한, 반대방향이 아래쪽으로 굴리는 경우는 다시 그 전 상태로 되돌아가기 때문에 그것 또한 무의마하게 된다. 그래서 결론적으로 오른쪽 왼쪽으로 굴릴수 있기에 전체 가지수는 4(맨처음) * 2^9 을 가지게 된다. 이러한 것을 가정으로 다음과 같은 로직으로 접근했다.
1. 전체 가지수 4 * 2^9을 전부 탐색 ( 4= 맨처음, 2=그 전에 굴린 방향과 그 맞은편에 있는 방향 제외)
2. 재귀 호출을 하여 재귀함수의 변수영역에 현재 map의 상태를 저장해놓고 되돌아오면 복원을 반복
3. 현재 map을 방향에 따라 먼저 굴려야할 공의 색깔을 정하여 굴리기 (예를 들면 위로 굴릴때 위에 있는 공부터 굴리기)
4. 파랑 혹은 빨강 공이 들어간다면 답 체크 및 그 이후의 가짓수를 안보도록 return
이 문제는 구현치고도 상당히 많은 요소를 꼼꼼히 체크 해줘야 했던 문제이다. 우선 문제에서 포인트는 맨처음 10번이하라는 조건이 주어졌을때 이것을 완전탐색으로 접근해야 했던 점이고, 2차원 배열의 백트래킹이기에 각 재귀에서 재귀함수의 변수로 temp들을 선언후 본래의 map이랑 data들을 백업해놓고 다음재귀호출, 그 후 다시 temp들을 이용하여 복원하는 점이 포인트였다. 또한, 나는 공을 굴릴때 공의 위치에 따라 먼저굴려야할 공을 정하였는데, 이것에 약간의 스킬을 적용하자면 R-B-R순서로 굴려도 같은 결과값을 가지고 올수 있다.
|
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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
|
package boj.practice;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_bj_13460_구슬탈출2 {
static int[] di= {-1,0,1,0};
static int[] dj= {0,1,0,-1};
static int[][] dirs= {{1,3},{0,2},{1,3},{0,2}};
static char[][] map;
static int R,C;
static int answer;
static Pos red,blue;
static class Pos{
int i,j;
Pos(int i,int j){
this.i=i;this.j=j;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R=Integer.parseInt(st.nextToken());
C=Integer.parseInt(st.nextToken());
map=new char[R][C];
red=null;
blue=null;
for(int i=0;i<R;i++) {
String str=br.readLine();
for(int j=0;j<C;j++) {
map[i][j]=str.charAt(j);
if(map[i][j]=='R') red=new Pos(i, j);
if(map[i][j]=='B') blue=new Pos(i, j);
}
}
answer=100;
dfs(0,-1,false);
if(answer!=100) {
System.out.println(answer);
}else {
System.out.println(-1);
}
}
static void dfs(int depth,int dir,boolean stop) {
if(depth==10 || stop==true) {
return;
}
char[][] tempMap=new char[R][C];
Pos tempRed=new Pos(0, 0);
Pos tempBlue=new Pos(0, 0);
if(dir==-1) {
for(int d=0;d<4;d++) {
storeData(tempMap,tempRed,tempBlue);
boolean s = moveMap(d,depth+1);
dfs(depth+1,d,s);
backupData(tempMap,tempRed,tempBlue);
}
}else {
for(int d : dirs[dir]) {
storeData(tempMap,tempRed,tempBlue);
boolean s = moveMap(d,depth+1);
dfs(depth+1,d,s);
backupData(tempMap,tempRed,tempBlue);
}
}
}
static boolean moveMap(int dir,int depth) {
Pos curRed=red;
Pos curBlue=blue;
boolean findRed=false;
boolean findBlue=false;
if(dir==0) {
if(curRed.i<curBlue.i) {
findRed=moveRed(dir);
findBlue=moveBlue(dir);
}else {
findBlue=moveBlue(dir);
findRed=moveRed(dir);
}
}else if(dir==1) {
if(curRed.j>curBlue.j){
findRed=moveRed(dir);
findBlue=moveBlue(dir);
}else {
findBlue=moveBlue(dir);
findRed=moveRed(dir);
}
}else if(dir==2) {
if(curRed.i>curBlue.i){
findRed=moveRed(dir);
findBlue=moveBlue(dir);
}else {
findBlue=moveBlue(dir);
findRed=moveRed(dir);
}
}else if(dir==3) {
if(curRed.j<curBlue.j){
findRed=moveRed(dir);
findBlue=moveBlue(dir);
}else {
findBlue=moveBlue(dir);
findRed=moveRed(dir);
}
}
if(findRed==true && findBlue==false) {
// System.out.println(depth+" "+dir+"pos:"+curRed.i+", "+curRed.j+" -- "+curBlue.i+", "+curBlue.j);
// for(int i=0;i<R;i++) {
// for(int j=0;j<C;j++) {
// System.out.print(map[i][j]+" ");
// }
// System.out.println();
// }
answer=Math.min(answer,depth);
return true;
}
if(findBlue==true)
return true;
return false;
}
static boolean moveRed(int dir) {
map[red.i][red.j]='.';
boolean find=false;
while(true) {
int nextI=red.i+di[dir];
int nextJ=red.j+dj[dir];
if(map[nextI][nextJ]=='#' || map[nextI][nextJ]=='B') {
map[red.i][red.j]='R';
break;
}
else if(map[nextI][nextJ]=='.') {
red.i=nextI;
red.j=nextJ;
}else if(map[nextI][nextJ]=='O') {
find=true;
break;
}
}
return find;
}
static boolean moveBlue(int dir) {
map[blue.i][blue.j]='.';
boolean find=false;
while(true) {
int nextI=blue.i+di[dir];
int nextJ=blue.j+dj[dir];
if(map[nextI][nextJ]=='#' || map[nextI][nextJ]=='R') {
map[blue.i][blue.j]='B';
break;
}
else if(map[nextI][nextJ]=='.') {
blue.i=nextI;
blue.j=nextJ;
}else if(map[nextI][nextJ]=='O') {
find=true;
break;
}
}
return find;
}
static void storeData(char[][] tempMap,Pos tempRed, Pos tempBlue) {
for(int i=0;i<R;i++) {
for(int j=0;j<C;j++) {
tempMap[i][j]=map[i][j];
}
}
tempRed.i=red.i;tempRed.j=red.j;
tempBlue.i=blue.i;tempBlue.j=blue.j;
}
static void backupData(char[][] tempMap,Pos tempRed, Pos tempBlue) {
for(int i=0;i<R;i++) {
for(int j=0;j<C;j++) {
map[i][j]=tempMap[i][j];
}
}
red.i=tempRed.i;red.j=tempRed.j;
blue.i=tempBlue.i;blue.j=tempBlue.j;
}
}
|
|
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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
|
package boj.practice;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main_bj_13460_구슬탈출2_2 {
static int[] di= {-1,0,1,0};
static int[] dj= {0,1,0,-1};
static int[][] dirs= {{1,3},{0,2},{1,3},{0,2}};
static char[][] map;
static int R,C;
static int answer;
static Pos red,blue;
static class Pos{
int i,j;
Pos(int i,int j){
this.i=i;this.j=j;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R=Integer.parseInt(st.nextToken());
C=Integer.parseInt(st.nextToken());
map=new char[R][C];
red=null;
blue=null;
for(int i=0;i<R;i++) {
String str=br.readLine();
for(int j=0;j<C;j++) {
map[i][j]=str.charAt(j);
if(map[i][j]=='R') red=new Pos(i, j);
if(map[i][j]=='B') blue=new Pos(i, j);
}
}
answer=100;
dfs(0,-1,false);
if(answer!=100) {
System.out.println(answer);
}else {
System.out.println(-1);
}
}
static void dfs(int depth,int dir,boolean stop) {
if(depth==10 || stop==true) {
return;
}
char[][] tempMap=new char[R][C];
Pos tempRed=new Pos(0, 0);
Pos tempBlue=new Pos(0, 0);
if(dir==-1) {
for(int d=0;d<4;d++) {
storeData(tempMap,tempRed,tempBlue);
boolean s = moveMap(d,depth+1);
dfs(depth+1,d,s);
backupData(tempMap,tempRed,tempBlue);
}
}else {
for(int d : dirs[dir]) {
storeData(tempMap,tempRed,tempBlue);
boolean s = moveMap(d,depth+1);
dfs(depth+1,d,s);
backupData(tempMap,tempRed,tempBlue);
}
}
}
static boolean moveMap(int dir,int depth) {
Pos curRed=red;
Pos curBlue=blue;
boolean findRed=false;
boolean findBlue=false;
findRed=moveRed(dir);
findBlue=moveBlue(dir);
findRed=moveRed(dir);
if(findRed==true && findBlue==false) {
answer=Math.min(answer,depth);
return true;
}
if(findBlue==true)
return true;
return false;
}
static boolean moveRed(int dir) {
map[red.i][red.j]='.';
boolean find=false;
while(true) {
int nextI=red.i+di[dir];
int nextJ=red.j+dj[dir];
if(map[nextI][nextJ]=='#' || map[nextI][nextJ]=='B') {
map[red.i][red.j]='R';
break;
}
else if(map[nextI][nextJ]=='.') {
red.i=nextI;
red.j=nextJ;
}else if(map[nextI][nextJ]=='O') {
find=true;
break;
}
}
return find;
}
static boolean moveBlue(int dir) {
map[blue.i][blue.j]='.';
boolean find=false;
while(true) {
int nextI=blue.i+di[dir];
int nextJ=blue.j+dj[dir];
if(map[nextI][nextJ]=='#' || map[nextI][nextJ]=='R') {
map[blue.i][blue.j]='B';
break;
}
else if(map[nextI][nextJ]=='.') {
blue.i=nextI;
blue.j=nextJ;
}else if(map[nextI][nextJ]=='O') {
find=true;
break;
}
}
return find;
}
static void storeData(char[][] tempMap,Pos tempRed, Pos tempBlue) {
for(int i=0;i<R;i++) {
for(int j=0;j<C;j++) {
tempMap[i][j]=map[i][j];
}
}
tempRed.i=red.i;tempRed.j=red.j;
tempBlue.i=blue.i;tempBlue.j=blue.j;
}
static void backupData(char[][] tempMap,Pos tempRed, Pos tempBlue) {
for(int i=0;i<R;i++) {
for(int j=0;j<C;j++) {
map[i][j]=tempMap[i][j];
}
}
red.i=tempRed.i;red.j=tempRed.j;
blue.i=tempBlue.i;blue.j=tempBlue.j;
}
}
|
반응형
'Algorithm' 카테고리의 다른 글
| [BOJ] 1747. 소수&팰린드롬 (0) | 2020.07.01 |
|---|---|
| [BOJ] 17825. 주사위 윷놀이 (0) | 2020.06.06 |
| [BOJ] 1525. 퍼즐 (0) | 2020.06.04 |
| [BOJ] 1967. 트리의 지름 (0) | 2020.06.03 |
| [BOJ] 14391. 종이 조각 (0) | 2020.06.03 |