[BOJ] 1525. 퍼즐(Python) / BFS

1525번: 퍼즐

신박한 느낌의 BFS 문제였다. 처음 문제 봤을 때 감조차 잡히지 않았다. 이게 어떻게 BFS 인지 이해가 되지 않아, 코드 말고 아이디어 만이라도 얻어야겠다 싶어 구글링 해보니.. 3*3 맵에 있는 숫자들을 문자열로 변환해서 0이 있는 곳 기준으로 숫자 바꿀 수 있는 위치로 바꿔주고 BFS로 뻗어나가며 타겟 문자열을 찾는 방식으로 접근해야 한다는 것을 깨달았다. 이 아이디어를 바탕으로 코드를 짜봤다.

# 아이디어 참고까지 30분, 문제 pass까지 1시간 30분/ 총 2시간 소요

• 사용 알고리즘 : BFS 최단 시간 알고리즘
• 3*3 맵의 9개 칸을 문자열로 바꿔 이 문자열이 target 문자열(미리 정의)이 될 때까지 너비우선 탐색한다.
• bfs() 함수에서
  • 이미 방문한 문자열이 있는지 체크하는 check를 set 자료구조(중복된 원소 없는 성질 이용, 문자열 있는지 O(1)시간으로 확인 가능)으로 생성, 시작 문자열을 넣는다.
  • 큐를 생성해 (시작 문자열, 이동 횟수)를 담아준다.
  • 큐에서 값을 꺼내며 그 때의 문자열(temp)이 타겟 문자열("123456780")과 같다면 이동 횟수(cnt) 리턴하고 종료
  • 문자열에서 0이 있는 인덱스를 3*3 맵 내 좌표로 변환한다.
  • 상하좌우 중 이동할 수 있는 위치를 찾고, 이를 다시 문자열에서 사용하는 0~8의 인덱스(nextIdx)로 변환
  • 위치 교환 쉽게 하기 위해 리스트로 변환, 숫자 교환 후 다시 문자열(nextTemp)로 변환
  • nextTemp 문자열이 이미 방문한 곳이면 continue
  • 첫 방문이라면 check Set에 추가하고, 재탐색을 위해 (nextTemp, cnt + 1)을 큐에 담는다.
  • 큐에 있는 값을 모두 검사했음에도 타겟 문자열을 만나지 못하면 -1 리턴하고 종료

 

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

---

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

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

def bfs():
    check = set([start])
    q = deque([(start, 0)])
    while q:
        temp, cnt = q.popleft()     # 현재 문자열, 이동 횟수
        if temp == "123456780":     # 타겟 문자열과 같으면 그 때의 이동 횟수 리턴
            return cnt

        idx = temp.index("0")   # 0인 곳의 인덱스 
        r, c = idx//3, idx%3    # 이차원 맵 내 좌표로 변환
        for d in range(4):      # 4방향 중 위치 바꿀 수 있는 곳
            nr = r + dr[d]
            nc = c + dc[d]
            if not (0 <= nr < 3 and 0 <= nc < 3):   # 범위 밖은 숫자 교환 불가
                continue

            nextTemp = list(temp)           # 위치 교환 쉽게 하기 위해 리스트로 변환
            nextIdx = nr * 3 + nc           # 위치 교환할 인덱스
            nextTemp[idx], nextTemp[nextIdx] = nextTemp[nextIdx], nextTemp[idx]
            nextTemp = ''.join(nextTemp)    # 문자열로 재변환
            
            if nextTemp in check:           # 이미 방문한 곳인지 확인
                continue
            check.add(nextTemp)				# 방문 표시
            q.append((nextTemp, cnt+1))		# (위치 교환한 문자열, 횟수+1)해서 큐에 담기

    return -1	# 불가능한 경우

# main
start = ""               # 시작 문자열
for _ in range(3):
    start += ''.join(list(input().split()))
print(bfs())

---

• 시간 : 492ms / 메모리 : 160648kb
• 고찰 :
  • 처음에 방문 체크를 하는 check를 안 만들어준 실수, 완전 바보같이 target 문자열을 처음 지정할 때 "0123456789"(10자리 문자열)로 해줘서 계속 답이 안 나왔다. 원인을 알고 나니 다 풀어놓고 이상한 데서 헤맨 게 열받았다;;ㅋㅋ
  • 문자열 인덱스와 3*3맵에서 사용하는 좌표로의 변환이 많았지만 나름대로 그 부분은 쉽게 풀어낼 수 있었다.
  • BFS는 결국 "탐색"의 방법 중 하나이다. 큐에서 값을 하나씩 꺼내며 가능한 경우를 찾아 변화한 내용을 다시 큐에 담아 퍼트리며 같은 방식으로 또 새롭게 가능한 경우의 수에 대해 탐색하는 방법인 것이다.
  • 한 마디로 알고 나니 간단한 BFS 문제였다.(는 Gold2였지만 말이다)
  • 반짝이는 아이디어를 낼 수 있도록 많은 문제를 풀어봐야겠다!
  • 재밌었다^______^