문제 링크 : https://www.acmicpc.net/problem/13460
남들은 다 BFS로 풀었는데 나혼자 삽질하면서 DFS로 풀었다. 덕분에 메모리도 메모리대로, 시간복잡도도 시간복잡도대로 잡아먹었지만 풀긴 풀었으니ㅠㅠㅠㅠㅠㅠㅠㅠ 익숙해지면 더 빨리 풀 수 있을 거라 믿는다(제발...ㅠ)
다음에 시간이 되면 BFS로도 짜봐야겠다
map이라는 객체를 생성한 다음 구슬을 한 칸 한 칸 굴려가면서 골인 지점에 도달했는지 확인하도록 코드를 작성했고 O R B 순서대로 있는 경우 성공, O B R 순서대로 있는 경우 실패라는 걸 염두에 두고 코드를 작성해야 한다! 이걸 모르고 그냥 둘 다 같은 행동 내에 떨어지면 실패라고 생각해서 초반에 삽질을 엄청 했다
개인적으로 이 문제에서 주의해야 할 건 각 timestep(탐색공간?) 마다 두 개의 구슬이 동시에 움직인다는 점. 나는 어차피 한 칸씩 굴렸기 때문에 구슬이 서로에 막혀서 통행이 불가능해진 경우를 if문으로 분기해서 짰지만 질문 란에 보면 다양하게 해결하는 방법이 많은 것 같다
제일 간단한건 각각 굴린 다음에 겹치는 경우에 따로 처리를 해 주는 것인 듯...?
package samsung;
import java.util.Scanner;
class Node{
int x, y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
public int getX(){
return x;
}
public int getY(){
return y;
}
public void setX(int x){
this.x = x;
}
public void setY(int y){
this.y = y;
}
public boolean isSame(int compx, int compy){
return (compx == x && compy == y);
}
}
public class Num13460 {
static char map[][];
public static void printMap(int N, int M){
int A = 0;
int B = 0;
for(int i = 0 ; i<N ; i++){
for(int j = 0 ; j < M ; j++){
System.out.print(map[i][j]);
if (map[i][j] == 'R'){
A = A+1;
}
else if(map[i][j] =='B'){
B = B+1;
}
}
if(A ==2 || B ==2){
System.out.print("");
}
System.out.println();
}
}
public static int DFS(int timestep, Node curR, Node curB, int goalx, int goaly){
if (timestep == 11){
return -1;
}
boolean isSucceed= false;
boolean isFail = false;
int up, down, right, left;
int N = map.length;
int M = map[0].length;
int redx = curR.getX();
int redy = curR.getY();
int bluex = curB.getX();
int bluey = curB.getY();
if(timestep == 7){
//System.out.println("A");
}
map[redx][redy] = '.';
map[bluex][bluey] = '.';
map[goalx][goaly] = 'O';
redx = curR.getX();
redy = curR.getY();
bluex = curB.getX();
bluey = curB.getY();
map[redx][redy] = 'R';
map[bluex][bluey] = 'B';
//up
int cnt = 0;
isFail = false;
while(cnt <= N){
if(map[redx-1][redy] == '.'){
map[redx][redy] = '.';
redx = redx - 1;
map[redx][redy] = 'R';
}
else if(map[redx-1][redy] == 'B'){
if(map[bluex-1][bluey] == '.'){
map[bluex][bluey] = '.';
bluex = bluex - 1;
map[bluex][bluey] = 'B';
map[redx][redy] = '.';
redx = redx - 1;
map[redx][redy] = 'R';
}
}
if(map[bluex-1][bluey] == '.'){
map[bluex][bluey] = '.';
bluex = bluex - 1;
map[bluex][bluey] = 'B';
}
else if(map[bluex-1][bluey] == 'R'){
if(map[redx-1][redy] == '.'){
map[redx][redy] = '.';
redx = redx - 1;
map[redx][redy] = 'R';
map[bluex][bluey] = '.';
bluex = bluex - 1;
map[bluex][bluey] = 'B';
}
}
if(map[redx-1][redy] == 'O'){
map[redx][redy] = '.';
redx = redx - 1;
}
if(map[bluex-1][bluey] == 'O'){
map[bluex][bluey] = '.';
bluex = bluex - 1;
}
if(redx == goalx && redy == goaly){
isSucceed = true;
}
if(bluex == goalx && bluey == goaly){
isSucceed = false;
isFail = true;
break;
}
cnt++;
}
////printMap(N, M);
if(isSucceed){
map[redx][redy] = '.';
map[bluex][bluey] = '.';
map[goalx][goaly] = 'O';
redx = curR.getX();
redy = curR.getY();
bluex = curB.getX();
bluey = curB.getY();
map[redx][redy] = 'R';
map[bluex][bluey] = 'B';
return timestep;}
if(!isFail){
if(timestep == 8 && redx == 1 && redy == 1){
////System.out.println("a");
////printMap(N,M);
}
if(timestep==2 && redy == 4){
//System.out.println("a");
}
up = DFS(timestep+1, new Node(redx, redy), new Node(bluex, bluey), goalx, goaly);
}
else{
up = -1;
}
//printMap(N,M);
map[redx][redy] = '.';
map[bluex][bluey] = '.';
map[goalx][goaly] = 'O';
redx = curR.getX();
redy = curR.getY();
bluex = curB.getX();
bluey = curB.getY();
map[redx][redy] = 'R';
map[bluex][bluey] = 'B';
//down
cnt = 0;
isFail = false;
while(cnt <= N){
if(map[redx+1][redy] == '.'){
map[redx][redy] = '.';
redx = redx + 1;
map[redx][redy] = 'R';
}
else if(map[redx+1][redy] == 'B'){
if(map[bluex+1][bluey] == '.'){
map[bluex][bluey] = '.';
bluex = bluex + 1;
map[bluex][bluey] = 'B';
map[redx][redy] = '.';
redx = redx + 1;
map[redx][redy] = 'R';
}
}
if(map[bluex+1][bluey] == '.'){
map[bluex][bluey] = '.';
bluex = bluex + 1;
map[bluex][bluey] = 'B';
}
else if(map[bluex+1][bluey] == 'R'){
if(map[redx+1][redy] == '.'){
map[redx][redy] = '.';
redx = redx + 1;
map[redx][redy] = 'R';
map[bluex][bluey] = '.';
bluex = bluex + 1;
map[bluex][bluey] = 'B';
}
}
if(map[redx+1][redy] == 'O'){
map[redx][redy] = '.';
redx = redx + 1;
}
if(map[bluex+1][bluey] == 'O'){
map[bluex][bluey] = '.';
bluex = bluex + 1;
}
if(redx == goalx && redy == goaly){
isSucceed = true;
}
if(bluex == goalx && bluey == goaly){
isSucceed = false;
isFail = true;
break;
}
cnt++;
}
////printMap(N, M);
if(isSucceed == true){
map[redx][redy] = '.';
map[bluex][bluey] = '.';
map[goalx][goaly] = 'O';
return timestep;}
if(!isFail){
if(timestep == 1 && redy ==4){
//System.out.println("A");
}
down = DFS(timestep+1, new Node(redx, redy), new Node(bluex, bluey), goalx, goaly);
}else{down = -1;}
//printMap(N,M);
//left
map[redx][redy] = '.';
map[bluex][bluey] = '.';
map[goalx][goaly] = 'O';
redx = curR.getX();
redy = curR.getY();
bluex = curB.getX();
bluey = curB.getY();
map[redx][redy] = 'R';
map[bluex][bluey] = 'B';
cnt = 0;
isFail = false;
while(cnt <= M){
if(map[redx][redy-1] == '.'){
map[redx][redy] = '.';
redy = redy - 1;
map[redx][redy] = 'R';
}
else if(map[redx][redy-1] == 'B'){
if(map[bluex][bluey-1] == '.'){
map[bluex][bluey] = '.';
bluey = bluey-1;
map[bluex][bluey] = 'B';
map[redx][redy] = '.';
redy = redy - 1;
map[redx][redy] = 'R';
}
}
if(map[bluex][bluey-1] == '.'){
map[bluex][bluey] = '.';
bluey = bluey-1;
map[bluex][bluey] = 'B';
}
else if(map[bluex][bluey-1] == 'R'){
if(map[redx][redy-1] == '.'){
map[redx][redy] = '.';
redy = redy - 1;
map[redx][redy] = 'R';
map[bluex][bluey] = '.';
bluey = bluey-1;
map[bluex][bluey] = 'B';
}
}
if(map[redx][redy-1] == 'O'){
map[redx][redy] = '.';
redy = redy - 1;
}
if(map[bluex][bluey-1] == 'O'){
map[bluex][bluey] = '.';
bluey = bluey-1;
}
if(redx == goalx && redy == goaly){
isSucceed = true;
}
if(bluex == goalx && bluey == goaly){
isSucceed = false;
isFail = true;
break;
}
cnt++;
}
// printMap(N, M);
if(isSucceed){
map[redx][redy] = '.';
map[bluex][bluey] = '.';
map[goalx][goaly] = 'O';
redx = curR.getX();
redy = curR.getY();
bluex = curB.getX();
bluey = curB.getY();
map[redx][redy] = 'R';
map[bluex][bluey] = 'B';
return timestep;
}
if(!isFail){
left = DFS(timestep+1, new Node(redx, redy), new Node(bluex, bluey), goalx, goaly);
}else{left = -1;}
//right
isFail = false;
cnt = 0;
map[redx][redy] = '.';
map[bluex][bluey] = '.';
map[goalx][goaly] = 'O';
redx = curR.getX();
redy = curR.getY();
bluex = curB.getX();
bluey = curB.getY();
map[redx][redy] = 'R';
map[bluex][bluey] = 'B';
while(cnt <= M){
if(map[redx][redy+1] == '.'){
map[redx][redy] = '.';
redy = redy + 1;
map[redx][redy] = 'R';
}
else if(map[redx][redy+1] == 'B'){
if(map[bluex][bluey+1] == '.'){
map[bluex][bluey] = '.';
bluey = bluey+1;
map[bluex][bluey] = 'B';
map[redx][redy] = '.';
redy = redy + 1;
map[redx][redy] = 'R';
}
}
if(map[bluex][bluey+1] == '.'){
map[bluex][bluey] = '.';
bluey = bluey+1;
map[bluex][bluey] = 'B';
}
else if(map[bluex][bluey+1] == 'R'){
if(map[redx][redy+1] == '.'){
map[redx][redy] = '.';
redy = redy + 1;
map[redx][redy] = 'R';
map[bluex][bluey] = '.';
bluey = bluey+1;
map[bluex][bluey] = 'B';
}
}
if(map[redx][redy+1] == 'O'){
map[redx][redy] = '.';
redy = redy + 1;
}
if(map[bluex][bluey+1] == 'O'){
map[bluex][bluey] = '.';
bluey = bluey+1;
}
if(redx == goalx && redy == goaly){
isSucceed = true;
}
if(bluex == goalx && bluey == goaly){
isSucceed = false;
isFail = true;
break;
}
cnt++;
}
//printMap(N, M);
if(isSucceed == true){
map[redx][redy] = '.';
map[bluex][bluey] = '.';
map[goalx][goaly] = 'O';
redx = curR.getX();
redy = curR.getY();
bluex = curB.getX();
bluey = curB.getY();
map[redx][redy] = 'R';
map[bluex][bluey] = 'B';
return timestep;}
if(!isFail){
right = DFS(timestep+1, new Node(redx, redy), new Node(bluex, bluey), goalx, goaly);
}else{right = -1;}
int ret = 11;
if(0<up && up < ret ){
ret = up;
}
if (0<down && down < ret){
ret = down;
}
if (0<left && left < ret){
ret = left;
}
if (0<right&& right < ret){
ret = right;
}
if(up == -1 && down == -1 && left == -1 && right == -1){
ret = -1;
}
map[redx][redy] = '.';
map[bluex][bluey] = '.';
redx = curR.getX();
redy = curR.getY();
bluex = curB.getX();
bluey = curB.getY();
map[redx][redy] = 'R';
map[bluex][bluey] = 'B';
return ret;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); //세로
int M = sc.nextInt(); //가로
int redx = 0;
int redy = 0;
int bluex=0;
int bluey=0;
int goalx=0;
int goaly=0;
map = new char[N][M];
sc.nextLine();
for(int i = 0 ; i<N ; i++){
char[] tmp = sc.nextLine().toCharArray();
for(int j = 0; j < M ; j++){
if (tmp[j] == 'R'){
redx = i;
redy = j;
}
else if(tmp[j] == 'B'){
bluex = i;
bluey = j;
}
else if(tmp[j] == 'O'){
goalx = i;
goaly = j;
}
map[i][j] = tmp[j];
}
}
Node curR = new Node(redx, redy);
Node curB = new Node(bluex, bluey);
int ans = DFS(1, curR, curB, goalx, goaly);
System.out.println(ans);
}
}
'algorithm' 카테고리의 다른 글
| [BOJ 16236] 아기 상어 (0) | 2019.04.09 |
|---|---|
| [BOJ14889] 스타트와 링크 (0) | 2019.03.28 |
| [BOJ 15686] 드래곤커브 (0) | 2019.03.27 |
| [BOJ 14502] 연구소 (0) | 2019.03.24 |
| [BOJ14890] 경사로 (0) | 2019.03.23 |
댓글