[BOJ] 1938. 통나무 옮기기(Python) / BFS

1938번: 통나무 옮기기

요 근래 나를 이렇게 오랫동안 힘들게 한 문제가 있던가..(는 미네랄.. 있긴 하구나) 근데 그것보다 훨씬 힘든 문제였다. 그럼에도 불구하고, 우주의 힘을 끌어모아 스스로 고민하고 코딩해 pass를 받아냈다. 뿌듯 :) 그치만 실전에서 이런 문제를 만났다? 그럼 진짜 빡셌을 듯 싶다..

# 3시간 40분 소요

어려웠던 이유는,

1) 통나무가 세로 방향일 때 5가지, 가로 방향일 때 5가지 조건이 모두 다르기 때문에 하드코딩 필요함.

2) 방문 체크를 관리하기가 까다로움

3) 자료구조 상태 관리

4) (내 기준) 미친 코드 길이..(원래 200줄이 훌쩍 넘었는데 줄였는데도 160줄..)

• 사용 알고리즘 : BFS 최단 시간 알고리즘
• Input 받으며 처음 통나무가 있는 위치 좌표들을 start에, 타겟 위치 좌표를 goal에 저장, 모두 "0"으로 바꿈
• checkDir() 함수에서 첫 통나무 방향이 세로 방향이면 0, 가로 방향이면 1로 리턴
• bfs() 시작하기 전, 전역 변수로 visited, q를 정의한다.
  • visited는 Set 자료구조로, (현재 통나무 좌표들) 의 방문 확인 용도로 사용
  • q 큐에는 (시작 좌표, 시작 방향, 이동 횟수)를 담음
• 가장 중요한 bfs() 함수
  • 큐에서 값을 하나씩 꺼내며
    • (현재 통나무 위치 좌표, 방향, 이동 횟수)에 대해
    • 크게 현재 통나무 위치가 세로(0), 가로(1)인지 조건문으로 구분하고,
    • 그 안에서 U, D, L, R, T 5가지 경우에 대해 일일이 조건문을 작성
    • 이동 가능한 곳이라면(flag), 새 위치를 방문 여부를 확인해, 첫 방문일 때만 visited에 넣고, 재검사를 위해 큐에 담는다.(checkVisited() 함수)
    • 특히, 회전(T) 일 때 좀 까다로운데, 범위와 통나무 좌우로 나무 있는지 확인하고, 큐에 담을 때 방향을 꼭 바꿔줘야 한다!(0이면 1, 1이면 0으로!!)
  • 큐에서 꺼낸 값이 목적지 좌표와 같다면, 이동 횟수를 리턴 후 종료
  • 큐에 있는 모든 값을 확인했는데도 목적지에 도착하지 못하면 0 리턴 후 종료

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline
from collections import deque

def checkDir(temp):
    if temp[0][1] == temp[1][1]:
        return 0    # 세로 방향 : 0
    return 1        # 가로 방향 : 1

def checkVisited(temp, d, cnt):
    if temp not in visited:   # 첫 방문
        visited.add(temp)
        q.append((temp, d, cnt+1))

def bfs():
    while q:
        newTemp, d, cnt = q.popleft()
        if newTemp == goal:     # 타겟 위치 도착
            return cnt

        if d == 0:      # 세로 방향일 때
            for cmd in range(5):
                # U
                if cmd == 0:
                    col = deque(newTemp)
                    r, c = col[0]
                    if (0 <= r-1 < N) and plain[r-1][c] == "0":
                        col.pop()
                        col.appendleft((r-1, c))
                        checkVisited(tuple(col), 0, cnt)

                # D
                elif cmd == 1:
                    col = deque(newTemp)
                    r, c = col[-1]
                    if (0 <= r+1 < N) and plain[r+1][c] == "0":
                        col.popleft()
                        col.append((r+1, c))
                        checkVisited(tuple(col), 0, cnt)

                # L
                elif cmd == 2:
                    flag = 1
                    for r, c in newTemp:
                        if not (0 <= c-1 < N) or plain[r][c-1] == "1":
                            flag = 0
                            break
                    if flag:
                        col = tuple([(r, c-1) for r, c in newTemp])
                        checkVisited(col, 0, cnt)

                # R
                elif cmd == 3:
                    flag = 1
                    for r, c in newTemp:
                        if not (0 <= c+1 < N) or plain[r][c+1] == "1":
                            flag = 0
                            break
                    if flag:
                        col = tuple([(r, c+1) for r, c in newTemp])
                        checkVisited(col, 0, cnt)

                # T
                else:
                    flag = 1
                    for r, c in newTemp:
                        if not (1 <= c < N-1):
                            flag = 0
                            break
                        if plain[r][c-1] == "1" or plain[r][c+1] == "1":
                            flag = 0
                            break
                    if flag:	# 가능한 경우
                        cr, cc = newTemp[1]     	# 중심 좌표
                        row = ((cr, cc-1), (cr, cc), (cr, cc+1))
                        checkVisited(row, 1, cnt)	# 방향 바꾸며 큐에 담기

        else:       # 가로 방향일 때
            for cmd in range(5):
                # U
                if cmd == 0:
                    flag = 1
                    for r, c in newTemp:
                        if not (0 <= r-1 < N) or plain[r-1][c] == "1":
                            flag = 0
                            break
                    if flag:
                        row = tuple([(r-1, c) for r, c in newTemp])
                        checkVisited(row, 1, cnt)

                # D
                elif cmd == 1:
                    flag = 1
                    for r, c in newTemp:
                        if not (0 <= r+1 < N) or plain[r+1][c] == "1":
                            flag = 0
                            break
                    if flag:
                        row = tuple([(r+1, c) for r, c in newTemp])
                        checkVisited(row, 1, cnt)

                # L
                elif cmd == 2:
                    row = deque(newTemp)
                    r, c = row[0]
                    if (0 <= c-1 < N) and plain[r][c-1] == "0":
                        row.pop()
                        row.appendleft((r, c-1))
                        checkVisited(tuple(row), 1, cnt)

                # R
                elif cmd == 3:
                    row = deque(newTemp)
                    r, c = row[-1]
                    if (0 <= c+1 < N) and plain[r][c+1] == "0":
                        row.popleft()
                        row.append((r, c+1))
                        checkVisited(tuple(row), 1, cnt)

                # T
                else:
                    flag = 1
                    for r, c in newTemp:
                        if not (1 <= r < N-1):
                            flag = 0
                            break
                        if plain[r+1][c] == "1" or plain[r-1][c] == "1":
                            flag = 0
                            break
                    if flag:
                        cr, cc = newTemp[1]
                        col = ((cr-1, cc), (cr, cc), (cr+1, cc))
                        checkVisited(col, 0, cnt)
    return 0

# main
N = int(input())
start, goal = [], [] 
plain = []
for r in range(N):
    plain.append(list(input().rstrip()))
    for c in range(N):
        if plain[r][c] == "B":
            start.append((r, c))
            plain[r][c] = "0"
        elif plain[r][c] == "E":
            goal.append((r, c))
            plain[r][c] = "0"

startDir = checkDir(start)  # 세로 방향 0, 가로 방향 1
goal = tuple(goal)
 
visited = set()             # 방문 정보 확인(set 자료구조)
visited.add(tuple(start))   # 첫 위치 방문 표시
q = deque([(start, startDir, 0)])       # (시작 좌표, 시작 방향, 이동 횟수)

print(bfs())

---

• 시간 : 312ms / 메모리 : 128580kb(PyPy3 제출)
• 고찰 : 정말 중간에 여러번 그만 둘까 고민했던 Gold2 문제인데, 끝까지 풀어내어 뿌듯했다ㅠㅠ 처음 알고리즘 시작할 때 DFS보다 BFS가 훨씬 쉽고 간단하다고 생각했는데, 전혀 아니었다. 이전 문제와 마찬가지로 탐색에 중점을 두고 상태 관리를 해주며 BFS를 푸는 건 정말 까다롭더라.. 3시간 30분 정도 걸렸는데, 정신줄 놓지 않고 끝까지 집중 또 집중하며 포기하지 않은 점에서 스스로 성장했음을 느꼈다. Keep Going!