📚 1525 - 퍼즐

퍼즐

이해

인덱스 → 행과열 : 행은 인덱스 // 3, 열은 인덱스 % 3
행과열 → 인덱스 : 인덱스는 행 * 3 + 열

💡 참고
sys.stdin.readline을 이용할 때, 하나의 단어로 사용하고 싶으면 read=sys.stdin.readline 이 후, read를 호출하면 된다. (다만, readline 관련 메소드들을 알고 싶다면 직접 readline을 호출해서 확인해야 한다.)

read().  # 이럴 경우 어떤 메서드를 호출할 수 있는지 잘 안나옴

replace() : 메서드를 사용하여 빈칸을 없앨 수 있다.

s = s.replace(' ', '').strip() # 공백제거

sys.stdin.readline()을 사용시, 뒤에 '\n'이 추가되므로, 한 줄로 문자열들을 추가하여 저장할 때는 strip()을 사용해야 한다.

visited = dict() : 방문한지 안한지 체크할 때, 딕셔너리 변수를 선언한다. 방문하지 않았는지 체크할 때는 get() 메서드를 선언하여 체크하면 된다.

이 문제에서 퍼즐 값들을 문자열로 처리하는 이유는 0이라는 숫자가 첫 번째 자리에 오게 되면, 숫자는 이를 없다고 판단하여 그 자리를 없애고 8개의 숫자로 구성하게 된다.

012345678 → 12345678
'012345678' → `12345678` 

➡️ 그러므로, 문자열로 처리해야 한다.

소스

import sys
from collections import deque

read = sys.stdin.readline

x_coordinate = [-1, 0, 1, 0]
y_coordinate = [0, 1, 0, -1]
table = ''

# 아홉 개의 수를 입력 받는다.
for _ in range(3):
    s = read()
    s = s.replace(' ', '')
    table += s.strip()


# bfs
def bfs():
    q = deque()
    q.append((table, 0))

    # 딕셔너리로, 방문한 지 안한지 key 값으로 판단한다.
    visited = dict()
    visited[table] = 1

    while q:
        # 퍼즐 9자리와, 현재 방문한 퍼즐 키 갯수를 확인한다.
        cur_puzzle, cur_cnt = q.popleft()

        # 찾았으면 끝!
        if cur_puzzle == '123456780':
            return cur_cnt

        # 0 인덱스를 찾는다.
        zero_index = cur_puzzle.index('0')
        cur_x = zero_index // 3  # 행
        cur_y = zero_index % 3  # 열

        # 상하좌우로 이동할 수 있는 곳 찾기
        for i in range(4):
            next_x = cur_x + x_coordinate[i]
            next_y = cur_y + y_coordinate[i]

            # 퍼즐 안이라면
            if 0 <= next_x < 3 and 0 <= next_y < 3:
                # 퍼즐은 일차원 배열에 저장할꺼기 때문에 (3 * 행 + 열)
                next_zero_index = next_x * 3 + next_y

                # list로 변환하여 해당 인덱스 값들을 교환한다.
                # str로 할 시 안됨!
                ct = list(cur_puzzle)
                ct[zero_index], ct[next_zero_index] = ct[next_zero_index], ct[zero_index]

                # 다시 list -> str로 자료형 변환한다.
                # 딕셔너리에서는 str을 key 값으로 가지고 있기 때문이다.
                so_next_puzzle = ''.join(ct)
                # 방문한 적 없는 곳이라면
                if not visited.get(so_next_puzzle):
                    # 방문 표시
                    visited[so_next_puzzle] = 1
                    # queue에 삽입한다.
                    q.append((so_next_puzzle, cur_cnt + 1))

    return -1


print(bfs())

채점 결과

아무래도, 2차원 배열을 어떻게 하면 간단하게 처리할 수 있을까? 라는 고민을 했었는데
검색을 하다가 이는 문자열로 처리하면 간단하게 할 수 있다는 것을 알게 되었다.
다음부터는 이를 참고하자!

참고 : https://zidarn87.tistory.com/255