코딩하는 덕구 🐶

105. [삼성기출1] Python 백준 13460 번 구슬 탈출 2 자세한 설명 본문

알고리즘 문제 풀이

105. [삼성기출1] Python 백준 13460 번 구슬 탈출 2 자세한 설명

코딩하는 덕구 🐶 2023. 3. 16. 15:44
728x90

안녕하세요 코딩하는 덕구입니다.

그래프 탐색 문제인 백준 13460 번 구슬 탈출 2 입니다.

https://www.acmicpc.net/problem/13460

 

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

 

 

먼저 백준 13460 번 구슬 탈출 2 파이썬 정답 코드입니다. 설명은 아래에 있습니다.

N, M = map(int, input().split())
visited = [ [[[False for _ in range(M)]for _ in range(N)]for _ in range(M)] for _ in range(N)]

board = [[]for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

#보드 입력
for i in range(N):
    board[i] = list(input())

#빨간공 R, 파란공 B 의 좌표
for i in range(N):
    for j in range(M):
        if board[i][j] == "R":
            rx = j
            ry = i
        elif board[i][j] == "B":
            bx = j
            by = i
visited[ry][rx][by][bx] = True

#보드를 기울였을 때 벽에 닿을 때 까지 이동
def move(y, x, dy, dx):
    distance = 0
    while board[y + dy][x + dx] != '#' and board[y][x] != "O":
        y += dy
        x += dx
        distance += 1
    return y, x, distance

#BFS를 이용한 탐색
def BFS(ry, rx, by, bx):
    cnt = 1
    queue = []
    queue.append((ry, rx, by, bx, cnt))

    while queue:
        ry, rx, by, bx, cnt = queue.pop(0)

        if cnt > 10:
            return -1

        for i in range(4):
            nry, nrx, disr = move(ry, rx, dy[i], dx[i]) #빨간공 이동
            nby, nbx, disb = move(by, bx, dy[i], dx[i]) #파란공 이동

            if board[nby][nbx] != "O": #실패가 아니고
                if board[nry][nrx] == "O": #성공이라면
                    return cnt

                if nry == nby and nrx == nbx: #겹친경우
                    if disr > disb:
                        nry = nry - dy[i]
                        nrx = nrx - dx[i]
                    else:
                        nby = nby - dy[i]
                        nbx = nbx - dx[i]
                        
                #방문하지 않았다면 방문처리 후 해당 노드 탐색
                if visited[nry][nrx][nby][nbx] == False:
                    visited[nry][nrx][nby][nbx] = True
                    queue.append((nry, nrx, nby, nbx, cnt + 1))
    
    #모든 노드 살펴봤는데 통과하지 못한 경우
    return -1

print(BFS(ry, rx, by, bx))

 

문제 요약

 

빨간 구슬, 파란 구슬이 들어있는 N X M 크기의 보드판에서 상 하 좌 우로 기울여

빨간 구슬만 보드판 안의 구멍에 넣어야되는데

이때 보드판을 최소 몇 번 기울여야되는지 출력하는 문제입니다.

파란 구슬이 구멍을 통해 나오거나 둘 다 나오게 되면 실패입니다.

 

문제 접근

BFS를 이용하여 최소 움직임 횟수를 구합니다.

이때 파란공이 나오지 않는 상태에서 빨간공이 나오면 그 횟수를 출력하고,

그 횟수가 11회 이상이면 -1을 출력합니다.

 

 

Python 코드 구현

 

먼저 보드의 세로, 가로 길이인 N, M 을 입력받습니다.

N, M = map(int, input().split())

  

빨간공, 파란공 모두 동시에 방문한 위치를 저장할 리스트를 선언합니다.

visited = [ [[[False for _ in range(M)]for _ in range(N)]for _ in range(M)] for _ in range(N)]

 

보드를 구현하고, 입력받습니다.

board = [[]for _ in range(N)]

#보드 입력
for i in range(N):
    board[i] = list(input())

 

보드를 탐색하며 빨간 구슬과, 파란 구슬의 좌표를 찾아내서 저장하고, 해당 좌표를 방문처리 합니다.

#빨간공 R, 파란공 B 의 좌표
for i in range(N):
    for j in range(M):
        if board[i][j] == "R":
            rx = j
            ry = i
        elif board[i][j] == "B":
            bx = j
            by = i
visited[ry][rx][by][bx] = True

 

x, y 방향 구현의 편의를 위해 리스트 dx, dy를 구현하고

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

 

보드를 기울였을 때 공의 위치와 이동거리를 알려주는 함수 move를 구현합니다. 

#보드를 기울였을 때 벽에 닿을 때 까지 이동
def move(y, x, dy, dx):
    distance = 0
    while board[y + dy][x + dx] != '#' and board[y][x] != "O":
        y += dy
        x += dx
        distance += 1
    return y, x, distance

 여기서 거리 distance는 공이 겹쳤을 때 예외처리를 하기 위해 정의 했습니다. 함수 BFS 에서 설명합니다.

 

구슬 탈출의 최소 거리를 출력하는 함수 BFS를 작성했습니다.

편의상 코드를 잘라서 설명합니다.

 

빨간공, 파란공의 좌표를 입력받고 BFS 탐색을 위한 queue,

보드 움직임 횟수를 저장하기 위한 cnt를 선언하고, queue안에 빨간 공 좌표, 파란공 좌표, 보드 움직임 횟수를 저장합니다.

def BFS(ry, rx, by, bx):
    cnt = 1
    queue = []
    queue.append((ry, rx, by, bx, cnt))

 

queue가 비어있지 않다면 == 탐색할 노드가 남아있다면

queue의 가장 앞쪽 성분을 가져와 좌표, 보드 조작횟수를 변수에 저장합니다.

만약 보드 조작횟수가 11 이상이면 -1을 return 합니다.

while queue:
    ry, rx, by, bx, cnt = queue.pop(0)

    if cnt > 10:
        return -1

 

빨간공과 파란공을 move 함수를 이용하여 상하좌우 한번씩 이동시키고, 각각의 좌표와 이동거리를 입력받습니다.

for i in range(4):
    nry, nrx, disr = move(ry, rx, dy[i], dx[i]) #빨간공 이동
    nby, nbx, disb = move(by, bx, dy[i], dx[i]) #파란공 이동

 

만약 파란공이 나오지 않은 상태에서 빨간공이 나오면 성공이므로 보드 조작 횟수를 출력합니다.

if board[nby][nbx] != "O": #실패가 아니고
    if board[nry][nrx] == "O": #성공이라면
        return cnt

 

두 공다 나오지 못한 상태라면 공이 겹쳐있는지 확인해줍니다.

보드에서 파란공과 빨간공은 같은 위치에 있을 수 없으므로

만약 위치가 같다면 이동거리가 긴 공이 다른 공 뒤에 있었다는 의미이므로 이동거리가 긴 공의 이동거리에서 -1 해줍니다.

if nry == nby and nrx == nbx: #겹친경우
    if disr > disb:
        nry = nry - dy[i]
        nrx = nrx - dx[i]
    else:
        nby = nby - dy[i]
        nbx = nbx - dx[i]

 

겹친 공 처리까지 완료된 상태에서 얻은 파란공, 빨간공의 좌표가 아직 방문하지 않은 좌표라면

방문처리 하고, queue에 삽입합니다.

이때 보드 조작 횟수를 하나 증가시켜줍니다.

#방문하지 않았다면 방문처리 후 해당 노드 탐색
if visited[nry][nrx][nby][nbx] == False:
    visited[nry][nrx][nby][nbx] = True
    queue.append((nry, nrx, nby, nbx, cnt + 1))

 

만약 queue가 아무 성분이 없을 때 까지 살펴보았다면 탈출이 불가능하다는 의미이므로 -1을 return 해 줍니다. 


#모든 노드 살펴봤는데 통과하지 못한 경우
return -1

 

 

백준 13460 번 구슬 탈출 2 Python 최종 코드입니다.

N, M = map(int, input().split())
visited = [ [[[False for _ in range(M)]for _ in range(N)]for _ in range(M)] for _ in range(N)]

board = [[]for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

#보드 입력
for i in range(N):
    board[i] = list(input())

#빨간공 R, 파란공 B 의 좌표
for i in range(N):
    for j in range(M):
        if board[i][j] == "R":
            rx = j
            ry = i
        elif board[i][j] == "B":
            bx = j
            by = i
visited[ry][rx][by][bx] = True

#보드를 기울였을 때 벽에 닿을 때 까지 이동
def move(y, x, dy, dx):
    distance = 0
    while board[y + dy][x + dx] != '#' and board[y][x] != "O":
        y += dy
        x += dx
        distance += 1
    return y, x, distance

#BFS를 이용한 탐색
def BFS(ry, rx, by, bx):
    cnt = 1
    queue = []
    queue.append((ry, rx, by, bx, cnt))

    while queue:
        ry, rx, by, bx, cnt = queue.pop(0)

        if cnt > 10:
            return -1

        for i in range(4):
            nry, nrx, disr = move(ry, rx, dy[i], dx[i]) #빨간공 이동
            nby, nbx, disb = move(by, bx, dy[i], dx[i]) #파란공 이동

            if board[nby][nbx] != "O": #실패가 아니고
                if board[nry][nrx] == "O": #성공이라면
                    return cnt

                if nry == nby and nrx == nbx: #겹친경우
                    if disr > disb:
                        nry = nry - dy[i]
                        nrx = nrx - dx[i]
                    else:
                        nby = nby - dy[i]
                        nbx = nbx - dx[i]

                #방문하지 않았다면 방문처리 후 해당 노드 탐색
                if visited[nry][nrx][nby][nbx] == False:
                    visited[nry][nrx][nby][nbx] = True
                    queue.append((nry, nrx, nby, nbx, cnt + 1))

    #모든 노드 살펴봤는데 통과하지 못한 경우
    return -1

print(BFS(ry, rx, by, bx))

 

 

백준 13460 번 구슬 탈출 2 자세한 설명 및 Python 코드였습니다.

감사합니다.

728x90
저작자표시 (새창열림)

'알고리즘 문제 풀이' 카테고리의 다른 글

107. [삼성기출3] Python 백준 3190 번 뱀 자세한 설명  (0) 2023.03.18
106. [삼성기출2] Python 백준 12100 번 2048 (Easy)자세한 설명  (0) 2023.03.17
101. 인공지능 기초 (2) AI, ML, DL, 인공지능 기초 용어  (0) 2023.02.06
100. 인공지능 기초 (1) 인공지능 필수 기초 수학  (0) 2023.01.28
99. 백준 11724 번 C++ 코드 및 자세한 설명  (0) 2023.01.21
'알고리즘 문제 풀이' Related Articles more