문제
세로크기 N, 가로크기 M의 보드가 존재한다. 보드에는 빈칸(공이 이동할 수 있는 공간)/벽(공이 이동할 수 없는 공간)/빨간 구슬 1개/파란 구슬 1개/구멍 1개가 주어집니다. 판을 상하좌우로 기울여서 구멍에서 뽑는데 최소 몇번 만에 빨간 구슬을 구멍에서 뽑을 수 있는지 구하는 문제입니다.
제약조건
- N,M 3 <= N,M <= 10
- 보드의 가장자리에는 벽이 있다.
- 기울이는 횟수가 10번 이상이거나 공을 빼낼수없는 경우 -1을 출력합니다.
- 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다.
풀이
판을 기울여서 어떤 물체를 움직이는 문제는 어떤 물체를 움직이는 기능을 하는 함수를 선언하면 편합니다.
먼저 전체적인 프로그램의 구성을 생각해봤습니다.
초기 위치를 Q에 넣습니다. 초기위치를 발견처리합니다.
while Q and 현재 기울인 횟수가 10보다 작은 경우:
기울인 횟수를 셉니다.
현재 Q의 크기만큼 반복합니다.
red의 위치, blue의 위치를 Q에서 꺼냅니다.
해당 위치에 대해서 상하좌우로 움직입니다.
움직인 위치가 blue를 떨어뜨리면 무시합니다.
움직인 위치가 red를 떨어뜨리면 정답을 반환합니다.
둘다 구멍에 위치하지 않는 경우 위치를 조정하고 큐에 넣습니다. 발견체크합니다.
전체적인 수도코드는 위와 같습니다. 이에 더해서 벽에 위치하기전까지 또는 구멍에 위치할때까지 구슬을 이동시키는 함수를 선언합니다.
구슬을 이동시키는 함수는 구슬을 움직이는데 있어서 벽과 구멍만을 고려합니다. 따라서 구슬의 위치 조정이 필요합니다. 주의해야할점은 두 구슬이 구멍에 위치할 경우 위치가 같은 경우가 생깁니다. 따라서 두 구슬이 구멍에 위치하는지 위치하지않는지에 대한 체크를 먼저하고 위치조정을 합니다.
구멍에는 두개의 공이 위치할수있습니다. 공이 구멍으로 빠졌으므로 판에 위치한것이 아니기 때문입니다. 다만 파란공이 빠졌기 때문에 답은 아닙니다.
구멍이 아닌 공간에는 두개의 공이 위치할수없습니다. 판에 위치하기 때문입니다. 따라서 구멍에 둘다 빠지지 않았으면서, 좌표가 겹치는 경우 위치 조정이 필요합니다.
위치 조정은 둘중 이동한 거리가 긴 공의 방향 이동을 한칸 무릅니다.
위 그림에서 파란색 공이 빨간색 공보다 이동거리가 한칸 더 많다는것을 확인할수있습니다. 따라서 파란색 공의 이동거리를 한칸 무릅니다.
코드
'''
Created by jun on 21/05/31
'''
import collections
#움직이고 싶은 marble의 위치, 움직이고 싶은 방향의 y, 움직이고 싶은 방향의 x
#가장 바깥 행과 열은 모두 막혀져 있다. (범위 체크하지 않아도 됨.)
#다 옮긴 후에는 옮겨진 marble의 위치, 움직인 길이를 반환한다.
#벽은 '#'으로 표현된다.
#원래 자리에서 움직일 위치가 '#'이면 안되고 원래 위치가 'O'이면 움직임을 멈춘다.
def move_marble(marble_position, dy, dx):
y, x = marble_position
moved_num = 0
while board[y+dy][x+dx] != '#' and board[y][x] != 'O':
moved_num += 1
y += dy
x += dx
return y, x, moved_num
N, M = map(int, input().split())
board = [list(input()) for _ in range(N)]
red_position = tuple()
blue_position = tuple()
for y in range(N):
for x in range(M):
if board[y][x] == 'R':
red_position = (y, x)
elif board[y][x] == 'B':
blue_position = (y, x)
#bfs로 푼다.
#초기 포지션에 대해 큐에 넣는다
Q = collections.deque()
Q.append((red_position, blue_position))
path = set((red_position, blue_position))
#빨강구슬을 빼내는것이다. 파랑구슬을 빼면 실패이다.
cnt = 0
#현재의 움직임이 11번째일때 while문을 탈출한다.
while Q and cnt < 10:
cnt += 1
for _ in range(len(Q)):
red_position, blue_position = Q.popleft()
#상하좌우로 움직인다.
for dy, dx in (-1, 0), (+1, 0), (0, -1), (0, +1):
n_red_y, n_red_x, n_moved_red = move_marble(red_position, dy, dx)
n_blue_y, n_blue_x, n_moved_blue = move_marble(blue_position, dy, dx)
#구멍은 두 구슬의 위치가 겹칠수있다.
#움직인 위치가 blue를 구멍에 떨어뜨릴때. -> 더이상 진행하지 않는다.
if board[n_blue_y][n_blue_x] == 'O':
continue
#움직인 위치가 red를 구멍에 떨어뜨릴때. -> 정답이다.
elif board[n_red_y][n_red_x] == 'O':
print(cnt)
exit()
#둘다 구멍에 위치하지 않는 경우. 위치가 겹치면 안된다.
#겹칠경우 구슬에 대해서 바로 직전의 포지션으로 돌릴 필요가 있다.
#길게 움직였다는것은 뒤에 있다는 뜻이다. 길게 움직인 marble의 위치를 한칸 무른다.
#같은 길이는 움직일수없다. (동일한 위치에 있었다는 이야기이므로.)
if n_red_y == n_blue_y and n_red_x == n_blue_x:
if n_moved_red > n_moved_blue:
n_red_y += -dy
n_red_x += -dx
else:
n_blue_y += -dy
n_blue_x += -dx
n_marble_position = ((n_red_y, n_red_x), (n_blue_y, n_blue_x))
#조정된 끝난 위치가 발견하지 않은 포지션인 경우 Q에 집어 넣는다.
if n_marble_position not in path:
#발견 완료
path.add(n_marble_position)
#Q에 넣는다.
Q.append(n_marble_position)
#현재의 움직임이 11번째 & 공이 움직이지 않을때
print(-1)새로 알게된 사실
판 유형 (판의 물체를 움직이는 유형)
