티스토리 뷰

PS/BOJ

[BOJ] 백준 13460번: 째로탈출 2

박트리 2017. 3. 31. 12:23

째로탈출 2


문제


N*M 보드에 파란 구슬 빨간 구슬 구멍이 한 개씩 있고, 상하좌우 4방향으로 기울일 수 있을 때, 최소 몇 번 만에 빨간 구슬이 구멍에 나올 수 있는지 출력하는 문제이다. 단, 파란 구슬이 구멍으로 같이 나오면 실패이다.



문제 풀이


최대 10번 까지 보드를 조작할 수 있으므로, BFS 탐색을 이용하면 각 상태 공간에서 상하좌우 4방향으로 전이 가능 하고, 한 상태 공간에서 해당 방향으로 최대 \(max(N,M)\) 만큼 이동할 수 있으므로 \(O(4^{10} max(N,M))\) 임을 알 수 있다. 따라서 각 상태 공간 내에서 한 방향으로 이동 할 때

1. 빨간 구슬과 파란 구슬이 일직선 상에 없음

1.1) 빨간 구슬이 가는 길에 구멍이 있는 경우 --> 탈출 성공

1.2) 파란 구슬이 가는 길에 구멍이 있는 경우 --> 탈출 실패

1.3) 구멍이 없는 경우 --> 구슬들을 최대한 이동한 후 큐에 push

2. 빨간 구슬이 가는 길에 파란 구슬이 있는 경우

2.1) 파란 구슬 앞에 구멍이 있는 경우 --> 탈출 성공

2.2) 파란 구슬 뒤에 구멍이 있는 경우 --> 탈출 실패

2.3) 구멍이 없는 경우 --> 파란 구슬은 최대한 이동, 빨간 구슬은 한 칸 덜 이동한 후에 큐에 push

3. 파란 구슬이 가는 길에 빨간 구슬이 있는 경우

3.1) 구멍이 있는 경우 --> 탈출 실패

3.2) 구멍이 없는 경우 --> 빨간 구슬은 최대한 이동, 파란 구슬은 한 칸 덜 이동한 후에 큐에 push

위의 과정을 bfs 각 상태 공간마다 시행하고 깊이가 10이 되면 종료하게 구현하면 된다.

 

소스 코드


'PS > BOJ' 카테고리의 다른 글

[BOJ] 백준 12100번: 2048(Easy)  (17) 2017.04.05
[BOJ] 백준 10875번: 뱀  (1) 2017.04.03
[BOJ] 백준 3653번: 영화 수집  (0) 2017.03.29
[BOJ] 백준 1941번: 소문난 칠공주  (2) 2017.03.27
[BOJ] 백준 10251번: 운전 면허 시험  (0) 2017.03.26
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
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
글 보관함