BOJ/13460_째로탈출2

[문제]

https://www.acmicpc.net/problem/13460

[처음 생각]

처음에는 맵을 보고 BFS로 풀어야겠다고 생각했는데, 빨간 구슬과 파란 구슬 모두를 움직여야 하므로 Queue가 2개여야 하나?? 라는 생각이 들었다. 

그래서 그럼 BFS로 풀지 않고 단순하게 시뮬레이션으로 구현하고 예외처리해주는식으로 문제를 풀려고 했다. 근데 그 안에서 벽/앞에 구슬이 막고 있을 때/구멍을 만났을 때로 나눠서 생각하려니 너무 복잡하고 알고리즘이 짜이지 않아서 애먹었다...

[풀이]

결국 째로탈출2 문제가 아닌 원래 째로탈출 문제의 코드를 참고해서 풀었다. 

BFS로 풀었고 나는 처음에 빨간 구슬과 파란 구슬을 한꺼번에 움직이기 위해서 while(true)문을 하나에 다 몰아서 쓰려고 했다. 

근데 여기서는 빨간 구슬과 파란 구슬을 일단 벽을 만나기전까지 같은 방향으로 각각 while문으로 최대한 움직여놓고 만약 둘 다 같은 칸에 존재한다면 그 때 둘 중에서 원래 있었던 위치를 고려해서 떼어놓는 방법으로 풀었다. 

그리고 빨간구슬의 좌표와 파란구슬의 좌표를 chk[][][][] 4차원 배열에 저장하면서 이미 방문한 위치라면 패스하고 그 다음으로 넘어간다. 왜냐면 이미 방문했던 방향은 제외해야 빠르게 찾을 수 있고 그래야 10번 이내에 못갈곳을 미리 알수있기 때문! 

-> 실제로 이 배열 없이 돌렸을 때 시간초과가 나고 굉장히 늦게 답이 나옴

[참고]

https://www.acmicpc.net/board/view/10402

-> 째로탈출 문제

[Code]

https://github.com/dbwls94/gomulsang/blob/youjin/BOJ/src/boj_13460/Escape22.java