해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 알고리즘 / 1525번 퍼즐 - BFS

www.acmicpc.net/problem/1525

문제 풀이

1525번 퍼즐 문제는 BFS(너비 우선 탐색)으로 풀 수 있는 문제입니다. 

퍼즐의 2차 배열 값을 문자열로 변환하여, 이 문자열을 가지고 BFS 탐색을 합니다. 

위에 변환된 문자열을 가지로 BFS 탐색을 할 때에, 배열에서 0을 기준으로 왼쪽,오른쪽,위,아래에 값을 교환하고, 그 배열의 값을 문자열로 변환시켜 queue에 넣습니다. 

queue에 넣은 문자열을 뺐을 때, 그 문자열이 '123456780'과 동일하다면 BFS 탐색을 종료하고, 이동 횟수를 반환하도록 합니다. 그 문자열이 '123456780'과 같지 않다면 또 0을 기준으로 왼쪽,오른쪽,위,아래에 값을 교환하여 탐색을 진행합니다. 

아래 코드는 문자열에서 '0'의 위치를 찾아, 왼쪽, 오른쪽, 위, 아래 값과 교환한 문자열을 만드는 부분으로 핵심 코드입니다. (puzzle_c -> puzzle_n으로 변경 )

그리고 주의할 점은 방문한 정보를 list 또는 queue에 넣을 수도 있는데, 시간 초과가 발생합니다. 

방문한 정보를 dictionary 자료 구조에 넣어 검색 속도를 빠르게 할 필요가 있습니다.  

#dictionary로 생성
visit = dict()

# 방문하지 않았다면, dictionary에 추가 
if not visit.get(puzzle_n):
	visit[puzzle_n] = 1
	queue.append((puzzle_n, time + 1))

전체 코드 

import sys
from collections import deque

#서, 북, 동, 남
dcol = [-1,  0, 1,  0]
drow = [0,  -1, 0,  1]

# s 문자열의 n번 항과 k번 항의 값을 교환
def swap(s, n, k):
    l = s[n]
    m = s[k]
    s = s[:k] + l + s[k+1:]
    s = s[:n] + m + s[n+1:]
    return s
# 벽 검사
def isRange(row, col):
	if col >= 3 or col < 0: return False
	if row >= 3 or row < 0: return False
	return True

def bfs(puzzle_s):
    result = -1
    queue = deque()
    queue.append((puzzle_s, 0))
    visit[puzzle_s] = 1

    while queue:
        puzzle_c, time = queue.popleft()

        #print(puzzle_c)
        if puzzle_c == target:
            result = time
            break
        pos = puzzle_c.find('0')
        row = pos//3
        col = pos%3
        #print("pos = ", pos, ", row = ", row, ", col = ", col)

        # 서, 북, 동, 남 방향으로 탐색
        for i in range(4):
            nrow = row + drow[i]
            ncol = col + dcol[i]

            #print("pos = ", pos, ", nrow = ", nrow, ", ncol = ", ncol)
            if isRange(nrow, ncol) is False:
                continue

            puzzle_n = puzzle_c
            puzzle_n = swap(puzzle_n, pos, nrow*3 + ncol)
            #print("new puzzle : ", puzzle_n)

            #방문했는지 검사, 방문하지 않았다면 visit 추가 및 queue에 문자열 추가
            if not visit.get(puzzle_n):
                visit[puzzle_n] = 1
                queue.append((puzzle_n, time + 1))
    return result

puzzle = ""
visit = dict()
for i in range(3):
	line = []
	line = list(map(int, sys.stdin.readline().split()))
	puzzle += str(line[0]) + str(line[1]) + str(line[2])

target = '123456780'
result_m = 0
result_m = bfs(puzzle)
print(result_m)