[백준/Python(파이썬)] 1525 퍼즐

문제

3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

1	2	3
4	5	6
7	8

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.

1		3
4	2	5
7	8	6

1	2	3
4		5
7	8	6

1	2	3
4	5
7	8	6

1	2	3
4	5	6
7	8

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

입력

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

출력

첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

풀이

최소 이동 횟수를 구하는 문제이므로 BFS를 사용한다.

빈칸을 표시하는 0을 9로 바꿈

방문 여부를 표시하기 위해 딕셔너리를 사용

key는 퍼즐의 형태, value는 퍼즐 이동 횟수를 저장함

빈 칸을 BFS의 큐에 넣고 상하좌우 좌표로 이동해서 퍼즐의 형태 변경, 이동 횟수 기록을 반복

23456789로 값이 떨어지거나 while문 조건을 만족하기 전 까지 계속 반복해서 수행함 

 

처음엔 최소 횟수를 구하래서 BFS인건 알겠는데 그래프를 어떻게 잡아야 할지 몰랐었음

한참 고민하다가 검색해보고 딕셔너리를 이용해서 푸는 방법을 떠올렸다

전에도 BFS문제중에서 이런식으로 딕셔너리를 이용하는 문제를 풀어본 적이 있었는데 바로 떠올리지 못했던걸보면 제대로 공부하지 못했나봄 복습해야겠다

어렵게 생각하지 말고 일단 떠오른 알고리즘 적용부터 해보기

소스코드

from collections import deque
def bfs():
    q = deque()
    q.append(aa)
    # 방문 표시를 위한 딕셔너리 사용
    # key : 퍼즐 형태, value : 퍼즐 이동 수
    visited[aa] = 0
    while q:
        v = q.popleft()
        if v == 123456789:
            return visited[v]
        s = str(v)
        target = s.find('9')
        # find : 문자열에서 지정한 문자가 몇 번째에 있는지 인덱스(index) 반환
        tx = target // 3
        ty = target % 3
        # 123485796 인 경우, 리스트 내 인덱스는 7
        # 123
        # 485
        # 796  <- (2, 1)
        for i in range(4):
            x = dx[i] + tx
            y = dy[i] + ty
            if 0 <= x < 3 and 0 <= y < 3:
                t = x*3 + y  # 3x3표에서 좌표를 리스트로 바꿨을 때의 인덱스 값
                ts = list(s)
                ts[target], ts[t] = ts[t], ts[target]  # swqp
                ti = int(''.join(ts))
                if not visited.get(ti):
                    visited[ti] = visited[v] + 1
                    q.append(ti)
    return -1

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
visited = dict()
aa = ''
for i in range(3):
    a = input()
    a = a.replace(' ', '')  # 공백 제거
    aa += a  # 문자열 더하기 연산 하려면 split() 으로 값 받을 수 x

aa = int(aa.replace('0', '9'))
print(bfs())

Git : github.com/jisun1125/algorithm-problem-solving/blob/main/baekjoon/no_1525.py

문제 : www.acmicpc.net/problem/1525