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

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

출처 : BAEKJOON ONLINE JUDGE

구슬 탈출2 (https://www.acmicpc.net/problem/13460)

처음 보시는 분들은 다음의 링크에서 문제 풀이를 꼭 봐주세요!! 백준 삼성 코딩 기출 문제 - 구슬 탈출 python(https://jeongchul.tistory.com/665)

문제 설명

이전 문제와 조건은 동일합니다. 보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성해야 합니다. 

문제 풀이

이전에 구슬의 움직이는 시도한 횟수(depth)를 출력하면 풀이는 끝납니다.

depth는 초기화를 1로 하였습니다. 처음의 움직임은 시도 1이니 1로 초기화해서 푸는게 쉽습니다.

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

이전의 풀이에서 출력이 성공하면 1, 실패하면 0인데 여기서는 depth를 출력하는 식으로 코드를 변경하면 됩니다.

단 실패하면 여기서는 0이 아닌 -1입니다.

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(depth)                 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(-1)

전체 코드입니다.

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(depth)                 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(-1) # 실패 bfs()