[백준] 13460 : 구슬 탈출 2 (파이썬)

BFS, 시뮬레이션 문제

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

---

 

이 문제를 풀며 모호했던 부분이 많았기 때문에 구현이 어려웠던 것 같다.

내가 이 문제를 풀며 모호함을 느꼈던 부분에 대해 먼저 소개하고자 한다.

 

헷갈렸던 부분

1. RB에 모두 왼쪽으로 기울이기를 수행했을 때 이동 후의 끝점이 .과 O일때의 차이

 

1) 예제입력2의 예시 - 이동 후의 끝점이 .(빈 칸)일때

 

" 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다.  "

따라서, RB에 모두 왼쪽으로 기울이기를 수행했을 때 RB는 동시에 같은 칸에 있을 수 없으므로 다음과 같은 형태로 이동한다. 

 

<초기>

7 7
#######
#...RB#
#.#####
#.....#
#####.#
#O....#
#######

출력
5

 

<왼쪽으로 기울이기 수행 후>

7 7
#######
#RB...#
#.#####
#.....#
#####.#
#O....#
#######

 

 

2) 예제입력5의 예시- 이동 후의 끝점이 O(구멍)일때

 

" 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. " 

O(구멍)은 .(빈 칸)과 달리 빨간 구슬과 파란 구슬이 모두 빠질 수 있다. 따라서, RB에 모두 왼쪽으로 기울이기를 수행했을 때 RB가 동시에 구멍에 빠지게 되므로 -1이 출력값이다.

3 10
##########
#.O....RB#
##########

출력 
-1

---

2. R과 B가 동시에 움직이는데, 각각 다른 방향으로 움직일 수도 있는가? -> X

"왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와
같은 네 가지 동작이 가능하다."
"각각의 동작에서 공은 동시에 움직인다."

1) 빨간 구슬과 파란 구슬이 동시에 같은 방향으로만 이동할 수 있다.

 

각각의 동작에서 공이 동시에 움직일 때, R과 B가 동시에 같은 방향으로만 움직여야 되는 것인지 의문이 들었다.

그렇지 않다면, R이 오른쪽 방향으로 움직일 때 B는 왼쪽 방향으로 움직이는 것이 가능한 것인가 ?

 

결론적으로 말하자면, 이 문제에서는 빨간 구슬과 파란 구슬이 동시에 같은 방향으로만 이동할 수 있다. 
즉, 한 번에 하나의 방향(왼쪽, 오른쪽, 위쪽, 아래쪽)으로 두 구슬을 동시에 움직여야 합니다.
구슬이 서로 다른 방향으로 이동할 수는 없다.

따라서, 각각의 동작(4방향)으로 기울일 시에 R과 B가 동시에 같은 방향으로만 움직일 수 있으므로 다음과 같이 코드를 짤 수 있겠다.

 for i in range(4): 
    nrx, nry = rx, ry
    while True:	
    	... # 빨간 구슬 움직임
    nbx, nby = bx, by
    while True: 
    	... # 파란 구슬 움직임
    if nrx == nbx and nry == nby: # 두 구슬의 위치가 같다면

 

 

2) 만약 빨간 구슬과 파란 구슬이 동시에 다른 방향으로도 이동할 수 있는 문제였다면 ?

 

처음에는 R과 B가 동시에 움직이는데, 각각 다른 방향으로도 움직일 수 있다고 생각하여 너무 어려웠다.

이 문제는 물음에 해당사항이 되지 않지만, 혹여나 가정을 해보자.

만약 빨간 구슬과 파란 구슬이 동시에 다른 방향으로 움직일 수 있다고 가정하면, 각각의 구슬에 대해 4방향의 움직임을 독립적으로 고려해야 한다. 즉, 이를 위해서는 이중 for문을 사용하여 각 구슬의 이동을 처리해야 할 것이다. 

 for i in range(4): 
    nrx, nry = rx, ry
    while True:	
    	... # 빨간 구슬 움직임
    
    for j in range(4):
        nbx, nby = bx, by
        while True: 
            ... # 파란 구슬 움직임
        
        if nrx == nbx and nry == nby: # 두 구슬의 위치가 같다면

 

다음과 같은 예시를 가정해보자.

만약 R과 B가 각각 다른 방향으로도 움직일 수 있다면 하나의 좌표에서 다음 좌표로 이동할 시 총 16가지의 경우의 수가 나올 것이다.

R이 →으로 움직일 때 : B가 →←↑↓

R이 ←으로 움직일 때 : B가 →←↑↓

R이 ↑으로 움직일 때 : B가 →←↑↓

R이 ↓으로 움직일 때 : B가 →←↑↓

7 7
#######
#..R.B#
#.#####
#.....#
#####.#
#O....#
#######

 

-> 문제를 푸는데 필요한 요구사항들이 명확하게 기입돼있지 않았다. 따라서, 문제를 이해하는데 오랜 시간이 걸렸다.

---

💡 풀이코드 (성공)

import sys 
from collections import deque 

N, M = map(int, sys.stdin.readline().split())

graph = []

marble = deque()
red = [0,0]
blue = [0,0]

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

for i in range(N):
    l = list(map(str, sys.stdin.readline().strip()))
    graph.append(l)
    for j in range(M):
        if l[j] == "R":
            red[0] = i 
            red[1] = j
        elif l[j] == "B":
            blue[0] = i 
            blue[1] = j

marble.append((red[0], red[1], blue[0], blue[1], 1))


def bfs(N, M, graph, red, blue, marble):
	# visited 배열 초기화
    visited = set()
    visited.add((red[0], red[1], blue[0], blue[1]))

    while marble: # 더 이상 구슬이 움직이지 않을 때 까지
        rr, rc, br, bc, cnt = marble.popleft()
        
        if cnt > 10: return -1

        for i in range(4):
            newRR = rr # 다음 좌표 초기화
            newRC = rc 
            while True: # 다음 좌표가 .이라면 계속 이동
                newRR += dy[i]
                newRC += dx[i]

                if graph[newRR][newRC] == "O": 
                    break 
                elif graph[newRR][newRC] == "#":
                    newRR -= dy[i] 
                    newRC -= dx[i]
                    break

            newBR = br # 다음 좌표 초기화
            newBC = bc

            while True: # 다음 좌표가 .이라면 계속 이동
                newBR += dy[i] 
                newBC += dx[i]

                if graph[newBR][newBC] == "O": 
                    break 
                elif graph[newBR][newBC] == "#":
                    newBR -= dy[i]
                    newBC -= dx[i]
                    break
             
            if graph[newBR][newBC] == "O": 
                continue 
            if newRR == newBR and newRC == newBC: 
                if abs(rr - newRR) + abs(rc - newRC) > abs(br - newBR) + abs(bc - newBC):
                    newRR -= dy[i]
                    newRC -= dx[i]
                else:
                    newBR -= dy[i]
                    newBC -= dx[i]

            if graph[newRR][newRC] == "O": return cnt

            if (newRR, newRC, newBR, newBC) not in visited:
                visited.add((newRR, newRC, newBR, newBC))
                marble.append((newRR, newRC, newBR, newBC, cnt + 1))

    return -1

print(bfs(N, M, graph, red, blue, marble))

 

주요 로직

1. 다음 좌표가 벽일 때

• 보통 같았으면 (구슬이 하나만 있었으면) 해당 구슬만 고려해도 되므로 다음 좌표가 벽이 아닐 시에만 조건을 걸어 큐에 바로 추가해주면 되었다.
• 그러나 이 문제에서는 두 개의 구슬을 고려해야 하므로, 각 구슬을 4방향으로 이동한 후 조건문을 통해 남아있는 구슬들만 큐에 삽입해야 한다. 
• 즉, 다음 좌표가 벽이라면 구슬을 벽에 도달하기 한 칸 전으로 돌려놓는다.

while True:
    elif graph[newRR][newRC] == "#":
        newRR -= dy[i] 
        newRC -= dx[i]
        break

 

+)

• 두개의 구슬 중 하나의 구슬이라도 움직였다면 다음 이동을 위해 큐에 삽입된다.
• 즉, 같은 방향으로 이동했을 때 두개의 구슬이 모두 막혀 이동을 하지 못하는 경우가 아니라면 하나의 구슬이 벽에 막히는 경우라도 다음 이동을 위해 큐에 삽입될 수 있다.
  따라서, #을 만났을 때 위와 같이 좌표를 벽에 부딪히기 전으로 돌려놓는 작업이 필요한 것이다.

 

2. 좌표가 구멍일 때 (순서 중요)

빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다.

 

파란 구슬이 구멍에 빠지면 실패이다.

빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다.

 

따라서, 파란 구슬이 구멍에 빠졌을 땐 밑의 로직을 아예 실행 안하게 continue 구문을 사용해주었다.

if graph[newBR][newBC] == "O": 
    continue 

if graph[newRR][newRC] == "O": return cnt

 

3. 빨간 구슬과 파란 구슬의 좌표가 같을 때의 처리

" 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다.  "

 

• 만약 다음좌표까지 이동한 거리가 빨간 구슬 > 파란 구슬이라면 빨간 구슬을 한칸 뒤로 돌려놓는다.
• 만약 다음좌표까지 이동한 거리가 빨간 구슬 < 파란 구슬이라면 파란 구슬을 한칸 뒤로 돌려놓는다.
• 다음 예를 생각해보면 어떤 로직인지 바로 이해가 갈 것이다.

<초기>

3 7
#######
#...RB#
#.#####

 

<왼쪽으로 기울이기 수행 후>

3 7
#######
#RB...#
#.#####

 

if newRR == newBR and newRC == newBC: 
    if abs(rr - newRR) + abs(rc - newRC) > abs(br - newBR) + abs(bc - newBC):
        newRR -= dy[i]
        newRC -= dx[i]
    else:
        newBR -= dy[i]
        newBC -= dx[i]

---

수정한 부분

1. red, blue 큐 -> marble 큐로 합침

초기에는 빨간 구슬 큐와 파란 구슬 큐를 따로 관리했다.

"기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다." 

따라서, 우리는 해당 루프를 빨간 구슬이 움직일 수 있을 때까지 혹은 파란 구슬이 움직일 수 있을 때까지 진행해야하므로 red, blue 큐로 각각 따로 분리하는 것은 비효율적이다. (예외처리 할게 많아지기 때문)

 

2. visited 배열

1) 초기 visited 배열의 위치

"시작점 -> #이나 O을 만나기 직전의 . "을 가기 위해 거쳐갔던 .들은 재방문해도 상관없다.

따라서, 아래의 위치에서 visited 배열 방문체크를 하면 원치 않은 결과를 초래한다.

def bfs(N, M, graph, red, blue, marble):
    visitedR = [[False] * M for _ in range(N)]
    visitedB = [[False] * M for _ in range(N)]
    visitedR[red[0]][red[1]] = True 
    visitedB[blue[0]][blue[1]] = True 

    while marble: 
        for i in range(4):
            while True:
            	# !!! visited 배열 방문체크 위치
                if visitedR[newRR][newRC] == False:
                    visitedR[newRR][newRC] = True

                    if graph[newRR][newRC] == "O": ...
                    elif graph[newRR][newRC] == "#": ...

 

2) 초기 visited 배열의 위치

⭐️  아래와 같이 작성하면 안되는 이유

• RB 둘다 방문한적이 있는 좌표라도 함께 방문했던 빨간구슬과 파란구슬의 쌍이 다르다면 또 방문하는 것이 가능하기 때문이다.
• 즉, 빨간 구슬과 파란 구슬의 좌표쌍을 함께 보고 방문체크를 해줘야 한다.

def bfs(N, M, graph, red, blue, marble):
    visitedR = [[False] * M for _ in range(N)]
    visitedB = [[False] * M for _ in range(N)]
    visitedR[red[0]][red[1]] = True 
    visitedB[blue[0]][blue[1]] = True 

    while marble: 
        for i in range(4):
            while True:

                    if graph[newRR][newRC] == "O": ...
                    elif graph[newRR][newRC] == "#": ...
             
            if graph[newBR][newBC] == "O": 
                continue 
            if newRR == newBR and newRC == newBC: ...
            if graph[newRR][newRC] == "O": return cnt
			
            # !!! visited 배열 방문체크 위치
            if visitedR[newRR][newRC] == False or visitedB[newBR][newBC] == False:
                visitedR[newRR][newRC] = True 
                visitedB[newBR][newBC] = True
                marble.append((newRR, newRC, newBR, newBC, cnt + 1))

    return -1

 

3) 변경 후

def bfs(N, M, graph, red, blue, marble):
	# !!! visited 배열 초기화 
    visited = set()
    visited.add((red[0], red[1], blue[0], blue[1]))

    while marble: 
        for i in range(4):
            while True:

                    if graph[newRR][newRC] == "O": ...
                    elif graph[newRR][newRC] == "#": ...
             
            if graph[newBR][newBC] == "O": 
                continue 
            if newRR == newBR and newRC == newBC: ...
            if graph[newRR][newRC] == "O": return cnt
			
            # !!! visited 배열 방문체크 위치
            if (newRR, newRC, newBR, newBC) not in visited:
                visited.add((newRR, newRC, newBR, newBC))
                marble.append((newRR, newRC, newBR, newBC, cnt + 1))

    return -1

 

3. 따로 도는 4방향 for문

이 부분은 문제를 잘못 이해했을 때 다음과 같이 R과 B가 각각 4방향 for문을 따로 돌았었다.

for문을 따로 돌고, if문도 for문의 바깥쪽에 있었기 때문에 당연하게도 제대로된 R과 B의 좌표 비교를 수행하지 못했다.

 for i in range(4): 
    nrx, nry = rx, ry
    while True:	
    	... # 빨간 구슬 움직임
        
 for j in range(4): 
    nbx, nby = bx, by
    while True: 
    	... # 파란 구슬 움직임
if nrx == nbx and nry == nby: # 제대로된 비교 못함

---

느낀점

 

문제의 요구사항을 정확하게 이해 후에 코드를 짜자
안그러면 디버깅이 힘들어지고, 문제의 요구사항이 바뀌는 순간 코드를 다시 갈아엎어야한다.

결론 : 문제를 잘 읽자

---

참고문헌

https://bgspro.tistory.com/70

백준 알고리즘 13460: 구슬 탈출 2 (Python)

https://hstory0208.tistory.com/entry/Python%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%B0%B1%EC%A4%80-13460-%EA%B5%AC%EC%8A%AC-%ED%83%88%EC%B6%9C2

[Python/파이썬] 백준 13460 - 구슬 탈출2

https://www.acmicpc.net/board/view/106418