13460. 구슬 탈출2 문제 바로가기
해결 방법
주요 과정
빨간 구슬과 파란 구슬의 위치를 변수에 저장하고 board에 “.”으로 바꾸어 이동할 수 있도록 한다.
moveBall함수를 통해 구슬을 굴려서 이동하는 경우를 찾도록 한다.deque를 이용하여 이동가능한 좌표를 q에 저장하여 BFS로 찾아준다.
이동 가능한 4가지 방향에 따라 pullBall 함수를 통해 방향에 따라 기울였을 때 굴러가는 최종 위치를 찾는다.
pullBall함수return 되는 값 중
move_cnt의 역할- 얼마나 움직였는지를 통해 빨간 구슬과 파란 구슬의 위치가 같을 경우 어떤 구슬을 후퇴시켜야 하는지 결정한다.
- “O” 목적지에 도착했으면 -1을 저장하여 목적지에 도착했는지 확인 가능하다.
굴렸을 때 위치 변화가 있을 경우 이동시켜주었다. (35번 코드 줄)
※ 주의 : 빨간 구슬의 위치변화만 살펴보고 위치 변화가 있을 때 파란 구슬을 이동시키며 확인했었다. (7%에서 틀렸습니다를 보게 될 것이다. 밑에 해당 반례 참고하세요!) 하지만 빨간 구슬은 이동이 없더라도 파란 구슬이 이동하여 원하는 조건을 만족시킬 수 있기에 빨간 구슬의 위치변화만 살펴보면 안된다!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
if [next_red_y, next_red_x, next_blue_y, next_blue_x] != [red_y, red_x, blue_y, blue_x]: # 움직임의 변화가 있었을 때만 확인하기(가지치기) if [next_red_y, next_red_x, next_blue_y, next_blue_x] not in visited: # 이동안했던 곳일 경우로 체크! if blue_cnt == -1: # 파란구슬이 구멍에 들어간 경우이기에 해당 경우 continue를 통해 확인하지 말기 continue if red_cnt == -1 and cnt + 1 <= 10: # 빨간구슬이 구멍에 들어간 경우 "종료 조건" answer = cnt + 1 return if [next_red_y, next_red_x] == [next_blue_y, next_blue_x]: # 같은 위치인 경우 if red_cnt > blue_cnt: # 빨간구슬이 더 많이 움직임 => 파란구슬 뒤에 있기에 빨간구슬을 후퇴시키기! next_red_y, next_red_x = next_red_y - dirs[d][0], next_red_x - dirs[d][1] else: # 파란구슬이 더 많이 움직임 => 빨간구슬 뒤에 있기에 파란구슬을 후퇴시키기! next_blue_y, next_blue_x = next_blue_y - dirs[d][0], next_blue_x - dirs[d][1] if cnt + 1 <= 10: # 10번 이하로 움직인 경우만 확인하면 되기에! q.append([next_red_y, next_red_x, next_blue_y, next_blue_x, cnt + 1]) visited.append([next_red_y, next_red_x, next_blue_y, next_blue_x])
파란 구슬이 구멍에 들어간 경우는 제외한다.
파란 구슬이 구멍에 안들어가고 빨간 구슬이 구멍에 들어가고 방향을 10번 이하로 바뀌었을 경우에 answer에 변경해주고 함수를 종료시킨다.
1번과 2번 조건이 아닌 경우
- 파란 구슬과 빨간 구슬의 위치가 같다면 이동수를 비교하여 많이 움직인 구슬을 뒤로 후퇴시킨다. (많이 움직였다는 것은 뒤에 있는 구슬이기 때문이다!)
방향을 10번 이하로 바꾼 경우라면 q에 추가하고 visited에 추가하여 되돌아가지 않도록 설정한다.
구현한 코드
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
from collections import deque
def pullBall(y, x, d): # 방향 d로 기울였을 때 굴러가는 최종 위치 찾아주는 함수
move_cnt = 0 # 얼마나 움직였는지 체크해주는 변수
ny, nx = y, x
while True:
ny, nx = ny + dirs[d][0], nx + dirs[d][1]
if 0 <= ny < N and 0 <= nx < M:
if board[ny][nx] == ".": # 빈칸이기에 이동하기
move_cnt += 1
y, x = ny, nx
elif board[ny][nx] == "O":
move_cnt = -1 # 목적지에 도착했다는 것을 -1로 저장
return ny, nx, move_cnt
else:
break
else:
break
return y, x , move_cnt
def moveBall(first_red_y, first_red_x, first_blue_y, first_blue_x): # 구슬을 굴려서 최종 O에 가는 곳을 구해주는 함수
global answer
q = deque()
visited = []
q.append([first_red_y, first_red_x, first_blue_y, first_blue_x, 0])
visited.append([first_red_y, first_red_x, first_blue_y, first_blue_x])
while q: # BFS 를 통해 이동 시키기
red_y, red_x, blue_y, blue_x, cnt = q.popleft()
for d in range(4):
# 각 방향별로 pullBall 함수를 통해 굴러간 마지막 위치 찾기
next_red_y, next_red_x, red_cnt = pullBall(red_y, red_x, d)
next_blue_y, next_blue_x, blue_cnt = pullBall(blue_y, blue_x, d)
if [next_red_y, next_red_x, next_blue_y, next_blue_x] != [red_y, red_x, blue_y, blue_x]: # 움직임의 변화가 있었을 때만 확인하기(가지치기)
if [next_red_y, next_red_x, next_blue_y, next_blue_x] not in visited: # 이동안했던 곳일 경우로 체크!
if blue_cnt == -1: # 파란구슬이 구멍에 들어간 경우이기에 해당 경우 continue를 통해 확인하지 말기
continue
if red_cnt == -1 and cnt + 1 <= 10: # 빨간구슬이 구멍에 들어간 경우 "종료 조건"
answer = cnt + 1
return
if [next_red_y, next_red_x] == [next_blue_y, next_blue_x]: # 같은 위치인 경우
if red_cnt > blue_cnt: # 빨간구슬이 더 많이 움직임 => 파란구슬 뒤에 있기에 빨간구슬을 후퇴시키기!
next_red_y, next_red_x = next_red_y - dirs[d][0], next_red_x - dirs[d][1]
else: # 파란구슬이 더 많이 움직임 => 빨간구슬 뒤에 있기에 파란구슬을 후퇴시키기!
next_blue_y, next_blue_x = next_blue_y - dirs[d][0], next_blue_x - dirs[d][1]
if cnt + 1 <= 10: # 10번 이하로 움직인 경우만 확인하면 되기에!
q.append([next_red_y, next_red_x, next_blue_y, next_blue_x, cnt + 1])
visited.append([next_red_y, next_red_x, next_blue_y, next_blue_x])
N, M = map(int, input().split())
board = [list(map(str, input())) for _ in range(N)]
answer = - 1
first_red_y = -1
first_red_x = -1
first_blue_y = -1
first_blue_x = -1
dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]] # 방향: 0-상 1-우 2-하 3-좌
for n in range(N):
for m in range(M):
# 구슬 위치 저장 후 움직일 수 있도록 빈칸으로 바꾸기
if board[n][m] == "R":
first_red_y, first_red_x = n, m
board[n][m] = "."
if board[n][m] == "B":
first_blue_y, first_blue_x = n, m
board[n][m] = "."
moveBall(first_red_y, first_red_x, first_blue_y, first_blue_x) # 구슬을 굴려서 최종 O에 가는 곳을 구해주는 함수
print(answer)
유용한 반례 모음
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
10 10
##########
#.BR.....#
#.#####..#
#.#...#..#
#.#.#.O..#
#.#.#....#
#.#....#.#
#.#..#...#
#.#......#
##########
answer=10
# 7%에서 틀렸습니다. 봤다면 위의 반례를 확인해보자!
3 5
#####
#OBR#
#####
answer=-1
5 7
#######
#.RB###
#.#.#O#
#.....#
#######
answer=4
11 13
#############
#.RB#########
#.#.........#
#.#.#######.#
#.#.#.....#.#
#.#.#..O#.#.#
#.#.#####.#.#
#.#.......#.#
#.#########.#
#...........#
#############
answer=-1 (11번)
11 13
#############
#RB##########
#.#.........#
#.#.#######.#
#.#.#.....#.#
#.#.#..O#.#.#
#.#.#####.#.#
#.#.......#.#
#.#########.#
#...........#
#############
answer=10