백준 삼성 코딩 기출 문제 - 구슬 탈출 python

백준 삼성 코딩 기출 문제 - 구슬 탈출 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()