백준 삼성 코딩 기출 문제 - 구슬 탈출 python
출처 : BAEKJOON ONLINE JUDGE
구슬 탈출(https://www.acmicpc.net/problem/13459)
문제 설명
보드가 N X M 크기로 있고, 중력을 통해서 떨어지기 때문에 기울이는 것을 통해서 위/아래/오른쪽/왼쪽으로 움직임이 가능합니다. 빨간 구슬(R)을 구멍(O)으로 움직여야 하고, 단 파란 구슬(B)가 구멍(O)으로 들어가거나 또는 같이 들어가도 실패합니다. 움직이는 횟수는 총 10번 이하로 제한되고 가능하면 1, 실패하면 0을 출력합니다.
문제 풀이
BFS(Breadth-First-Search) 알고리즘은 queue(FIFO -> deque사용)과 while(무한 루프)를 사용해 탐색을 구현합니다. DFS(Depth First Search) 알고리즘은 stack(LIFO)과 재귀 함수 사용해 구현해야 합니다.
여기서는 BFS 알고리즘을 통해서 탐색을 진행합니다.
[1] 전체 행렬의 row에 해당하는 n, column의 크기는 m 그리고 보드인 board 입력을 받습니다.
- from sys import stdin을 이용해서 입력을 받습니다.
from sys import stdin
from collections import deque
input = stdin.readline
n, m = map(int, input().split())
board = [list(input().strip()) for _ in range(n)] |
- board를 출력하면 다음과 같은 형태로 저장됩니다.
[2] 빨간 구슬, 파란 구슬 2개가 동시에 움직이므로, 각 2개의 구슬 x, y좌표를 visited 배열에 4차원으로 선언하고 False로 초기화합니다. 그리고 while문을 통해 bfs 탐색을 진행하면서 방문 여부를 확인하고 방문을 안했다면 queue에 넣고, True로 체크하게 됩니다.
visited = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)] |
[3] 구슬이 움직일 수 있는 x, y의 좌표를 만들고, collection의 deque를 이용해 queue를 생성합니다.
from collections import deque
dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1) # 각각 왼쪽 / 위쪽 / 오른쪽 / 아래쪽 x,y 좌표를 의미한다.
q = deque() |
[4] 보드에서 빨간 구슬(R)과 파란 구슬(B)가 어느 x, y 좌표에 있는지가 중요합니다.
- 문자열 비교를 통해 x, y 위치를 가져오고, queue에 넣을 때는 현재 몇 번 구슬을 움직 였는 지에 대한 정보를 저장하는 depth를 저장합니다. depth는 1로 초기화합니다.
- 따라서 큐에는 (빨간 구슬 x, y, 파란 구슬 x, y, 몇 번 구슬 움직였는지 )가 들어가게 되죠. 또한 visited 배열에 해당 구슬 정보를 True로 넣고 값을 업데이트합니다.
def init():
rx, ry, bx, by = [0] * 4 # 초기화 0, 0, 0, 0
for i in range(n):
for j in range(m):
if board[i][j] == 'R': # board에 빨간 구슬이라면 좌표 값 저장
rx, ry = i, j
elif board[i][j] == 'B': # board에 파란 구슬이라면 좌표 값 저장
bx, by = i, j
print(rx, ry, bx, by)
q.append((rx, ry, bx, by, 1)) # 위치 정보와 depth
visited[rx][ry][bx][by] = True |
[5] 다음은 구슬이 움직임이 가능하기 때문에 move라는 함수로 구현을 합니다.
- 벽(#) 또는 구멍(O)이 아닐 때 까지 정해진 방향으로 전진합니다.
- 여기서 이동한 칸 수를 저장하는 count라는 변수가 있습니다. 이 변수는 depth와는 전혀 상관이 없고, 빨간 구슬과 파란 구슬이 겹쳐서는 안된다라는 조건을 풀기 위해 쓰이는 변수입니다.
- 같은 방향으로 움직이는 가운데 2개의 구슬이 겹친다는 조건이면 둘 중 하나의 구슬의 움직이는 칸 수를 하나 줄여야 됩니다. 따라서 같이 움직이지만 서로 겹치지 않겠죠. 움직임이 가장 많은 구슬이 한 칸 적어야할 것입니다. 이를 판단하기 위해 count에 움직인 칸 수를 저장합니다.
def move(x, y, dx, dy):
count = 0 # 이동한 칸 수
# 다음 이동이 벽이거나 구멍일 때까지
while board[x+dx][y+dy] != '#' and board[x][y] != 'O':
x += dx
y += dy
count = 1
return x, y, count |
[6] 핵심인 bfs 탐색입니다.
- 큰 구조로는 초기화를 하고, queue에 값이 없을 때 까지 while문을 돌게 됩니다.
- while 문 안에서는 popleft()를 통해서 FIFO 구조에 따라 처음에 위치한 값을 가지고 옵니다.
- 10번 이하여야 한다는 조건을 먼저 봅니다. 넘어서면 break로 while문을 종료해버립니다.
- 다음으로는 4방향으로 움직일 수 있는지 시도를 해야 합니다. move를 써서 이동합니다.
- 이동한 x, y좌표 값을 토대로 판단을 진행합니다. 파란 구슬(B)이 구멍(O)에 떨어졌다면 실패이므로 continue문으로 넘어갑니다.
- 위의 조건을 지나면, 파란 구슬이 안떨어진 경우이며, 빨간 구슬(R)이 구멍(O)에 떨어졌다면 성공이므로 print(1)을 하고 return 문으로 반복문을 종료 함수의 결과값을 리턴합니다.
- 만약에 빨간 구슬과 파란 구슬이 겹쳐진다면, count(구슬이 움직인 칸 수)를 기반으로 많이 움직인 구슬을 현재 방향 기준으로 뒤로 한칸 물립니다.
- 마지막은 방문 여부를 확인합니다. 방문하지 않았다면 visited 배열에서 True로 체크하고 queue에 넣습니다.
- 10번을 넘어 버리면 실패이므로 print(0)을 출력하고 마칩니다.
def bfs():
init()
while q: # BFS -> queue, while
rx, ry, bx, by, depth = q.popleft()
if depth > 10: # 10 이하여야 한다.
break
for i in range(len(dx)): # 4방향으로 시도한다.
next_rx, next_ry, r_count = move(rx, ry, dx[i], dy[i]) # RED
next_bx, next_by, b_count = move(bx, by, dx[i], dy[i]) # BLUE
print("depth : ", depth, "direction : ", dx[i], dy[i], 'RED', next_rx, next_ry, 'BLUE', next_bx, next_by)
if board[next_bx][next_by] == 'O': # 파란 구슬이 구멍에 떨어지지 않으면(실패 X)
continue
if board[next_rx][next_ry] == 'O': # 빨간 구슬이 구멍에 떨어진다면(성공)
print(1)
return
if next_rx == next_bx and next_ry == next_by : # 빨간 구슬과 파란 구슬이 동시에 같은 칸에 있을 수 없다.
if r_count > b_count: # 이동 거리가 많은 구슬을 한칸 뒤로
next_rx -= dx[i]
next_ry -= dy[i]
else:
next_bx -= dx[i]
next_by -= dy[i]
# BFS 탐색을 마치고, 방문 여부 확인
if not visited[next_rx][next_ry][next_bx][next_by]:
visited[next_rx][next_ry][next_bx][next_by] = True
q.append((next_rx, next_ry, next_bx, next_by, depth +1))
print(0) |
첫 번째 테스트 케이스를 보죠.
보는 입장에서는 빨간 구실이 오른쪽으로 한 칸으로 이동하면 성공입니다.
배열로 구성된 보드를 움직이려면 row 인덱스에 해당하는 0이고, column 인덱스에 해당하는 1이면 오른쪽으로 움직입니다. x, y 좌표계에 따라서 x로 +1이동하면 되는거 아닌가.. 헷갈립니다. 그런 경우를 방지하고자 row와 column 인덱스를 생각해보세요.
- row 인덱스는 0번째 인덱스로 시작해 +1이면 아래로, -1이면 위로 움직입니다.
- column 인덱스는 0번째 인덱스로 시작해 오른쪽으로는 +1 왼쪽으로는 -1을 해야 움직입니다.
2번째 케이스도 비슷합니다.
전체 코드
from sys import stdin
from collections import deque
input = stdin.readline
n, m = map(int, input().split())
board = [list(input().strip()) for _ in range(n)]
visited = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)]
dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1)
q = deque()
def init():
rx, ry, bx, by = [0] * 4 # 초기화 0, 0, 0, 0
for i in range(n):
for j in range(m):
if board[i][j] == 'R': # board에 빨간 구슬이라면 좌표 값 저장
rx, ry = i, j
elif board[i][j] == 'B': # board에 파란 구슬이라면 좌표 값 저장
bx, by = i, j
q.append((rx, ry, bx, by, 1)) # 위치 정보와 depth
visited[rx][ry][bx][by] = True
def move(x, y, dx, dy):
count = 0 # 이동한 칸 수
# 다음 이동이 벽이거나 구멍이 아닐 때까지
while board[x+dx][y+dy] != '#' and board[x][y] != 'O':
x += dx
y += dy
count += 1
return x, y, count
def bfs():
init()
while q: # BFS -> queue, while
rx, ry, bx, by, depth = q.popleft() # FIFO
if depth > 10: # 10 이하여야 한다.
break
for i in range(len(dx)): # 4방향으로 시도한다.
next_rx, next_ry, r_count = move(rx, ry, dx[i], dy[i]) # RED
next_bx, next_by, b_count = move(bx, by, dx[i], dy[i]) # BLUE
if board[next_bx][next_by] == 'O': # 파란 구슬이 구멍에 떨어지지 않으면(실패 X)
continue
if board[next_rx][next_ry] == 'O': # 빨간 구슬이 구멍에 떨어진다면(성공)
print(1)
return
if next_rx == next_bx and next_ry == next_by : # 빨간 구슬과 파란 구슬이 동시에 같은 칸에 있을 수 없다.
if r_count > b_count: # 이동 거리가 많은 구슬을 한칸 뒤로
next_rx -= dx[i]
next_ry -= dy[i]
else:
next_bx -= dx[i]
next_by -= dy[i]
# BFS 탐색을 마치고, 방문 여부 확인
if not visited[next_rx][next_ry][next_bx][next_by]:
visited[next_rx][next_ry][next_bx][next_by] = True
q.append((next_rx, next_ry, next_bx, next_by, depth +1))
print(0) # 실패
bfs() |
