백준 1525번 - 퍼즐

출처 : 1525번: 퍼즐 (acmicpc.net)

1525번: 퍼즐

 

퍼즐 성공분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

1 초

32 MB (하단 참고)

10699

4514

2714

40.489%

문제

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을 출력한다.

 

---

[ 문제 설명 ]

 

 

그림으로 설명하겠다.

 

그림 1 - 퍼즐 문제 해결 아이디어

그림 2 - 퍼즐 문제 해결 아이디어

그림 3 - 퍼즐 문제 해결 아이디어

 

---

 

[ 코드 ]

 

# print("ヾ(❀^ω^)ﾉﾞ")

import sys
from collections import deque

# 왼, 아래, 오, 위
dcol = [-1, 0, 1, 0]
drow = [0, -1, 0, 1]


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


def bfs(puzzle_s):
    res = -1
    queue = deque()
    queue.append((puzzle_s, 0))
    visited[puzzle_s] = 1
    # print(visited)
    # print(queue)

    while queue:
        puzzle_c, cnt = queue.popleft()
        # print(puzzle_c, cnt)
        if puzzle_c == target:  # 원하는 형태가 나온 경우
            res = cnt
            break
        pos = puzzle_c.find("0")  # 0 에서 움직일 수 있으므로, 찾는 것
        # print(pos)
        row = pos // 3  # 행
        col = pos % 3  # 열

        for i in range(4):
            nrow = row + drow[i]
            ncol = col + dcol[i]

            print(nrow, nrow * 3 + ncol)

            if isRange(nrow, ncol) is False:
                continue

            puzzle_n = puzzle_c
            # print(nrow * 3 + ncol)
            puzzle_n = swap(puzzle_n, pos, nrow * 3 + ncol)

            if not visited.get(puzzle_n):
                visited[puzzle_n] = 1
                queue.append((puzzle_n, cnt + 1))

    return res


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

target = "123456780"
res_m = 0
res_m = bfs(puzzle)
print(res_m)

 

 

---

후기

 

복습하면서 처음에는 왜 배열화를 할까 가

확실하게 이해되지 않았는데

복습하면서 확실하게 알게 되었음.