[백준] 1525번 - 퍼즐 / 골드 2 / 파이썬 풀이

문제 링크

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

1525번: 퍼즐

 

시간 제한 : 1초

메모리 제한 : 32 MB

 

문제 요약

맞춰져야 하는 퍼즐

주어진 초기 상태의 퍼즐

 

• 문제 : 초기 상태의 퍼즐이 주어졌을 때, 맞춰져야 하는 형태로 되기까지의 퍼즐 최소 이동횟수를 구하기.
  
  
• 종료 조건
  - 빈칸을 표시하는 0을 9로 바꾼다면, 123456789와 같은 문자열이 나온다면 퍼즐이 올바르게 맞춰진 것이므로 종료.
  - 퍼즐을 맞추는 과정 중에, 동일한 문자열이 2번 이상 나온다면 해당 퍼즐은 맞출 수 없는 퍼즐이므로, -1을 출력하여 프로그램 종료.

 

입력

예제 입력 1

1 0 3
4 2 5
7 8 6

예제 입력 2

3 6 0
8 1 2
7 4 5

 

출력

예제 출력 1

3

예제 출력 2

-1

---

풀이

 

"BFS를 활용하는데, 이때 퍼즐의 좌표와 인덱스가 몫과 나머지로 표현될 수 있음을 생각해보자!"

from collections import deque

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'))      # 예제 입력 1로 보면 aa에는 193425786이 저장됨.


def bfs():
    q = deque()
    q.append(aa)
    # 방문 표시를 위한 딕셔너리 사용
    # key : 퍼즐 형태, value : 퍼즐 이동 수
    visited[aa] = 0

    while q:
        popped_number = q.popleft()
        if popped_number == 123456789:
            return visited[popped_number]        # '123456789'가 되기까지의 퍼즐 이동횟수 반환

        s = str(popped_number)
        present_zero_index = s.find('9')
        # find : 문자열에서 지정한 문자가 몇 번째에 있는지 인덱스(index) 반환
        zero_x = present_zero_index // 3
        # 문자열에서의 '9'의 인덱스를 3으로 나눈 몫
        # -> target이 x 좌표(0부터 시작)에서 어느 위치에 있는지를 알 수 있음.

        zero_y = present_zero_index % 3
        # 문자열에서의 '9'의 인덱스를 3으로 나눈 나머지
        # -> target이 y 좌표(0부터 시작)에서 어느 위치에 있는지를 알 수 있음.

        # ex) 123485796 인 경우, 리스트 내 인덱스는 7
        # 123
        # 485
        # 796
        # 위와 같이 볼 때 9는 (2,1) 좌표에 있다고 판단.

        for i in range(4):
            next_x = zero_x + dx[i]
            next_y = zero_y + dy[i]
            if 0 <= next_x < 3 and 0 <= next_y < 3:
                next_zero_index = next_x * 3 + next_y
                # 3x3표에서 좌표를 리스트로 바꿨을 때의 인덱스 값

                changed_number_string = list(s)
                changed_number_string[present_zero_index], changed_number_string[next_zero_index] \
                    = changed_number_string[next_zero_index], changed_number_string[present_zero_index]   # swap

                for_dict_int = int(''.join(changed_number_string))
                
                if not visited.get(for_dict_int):		# 해당 숫자배열의 값이 없다면(=여태껏 나온 숫자배열이 아니라면)
                    visited[for_dict_int] = visited[popped_number] + 1		
				# 퍼즐을 이동시키기 전, 지금까지의 퍼즐을 움직인 횟수 + 1
                    q.append(for_dict_int)	# 다시 큐에 넣어줌.
    return -1


print(bfs())

 

참고

https://jshong1125.tistory.com/41

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