[BaekJoon] 백준 3041 N-퍼즐 (Python / 파이썬)

BaekJoon 백준 3041 N-퍼즐 문제는 15-퍼즐은 4*4 보드에서 움직일 수 있는 정사각형으로 이루어져 있고, 한 정사각형은 빠져있다. 각 정사각형의 현재 위치와 퍼즐을 풀었을 때의 위치와의 거리의 합인 흩어짐 정도를 구하는 문제이다. 난이도는 Bronze 1이다.

 

BaekJoon 3041 N-퍼즐 문제 정보

출처

- https://www.acmicpc.net/problem/3041

알고리즘 분류

- 구현

난이도

- 브론즈 1 / Bronze 1

 

N-퍼즐 문제 요약

• 15-퍼즐은 4*4 보드에서 움직일 수 있는 정사각형으로 이루어져 있고, 한 정사각형은 빠져있다. 정사각형은 A부터 O까지 이름이 붙여져 있다. 
• 우리는 이러한 15-퍼즐에서 흩어짐 정도를 계산할 수 있다. 흩어짐 정도는 각 정사각형의 현재 위치와 퍼즐을 풀었을 때의 위치와의 거리의 합이다.
• 두 정사각형의 거리는 그 두 정사각형 사이의 맨해튼 거리이다.
• 15-퍼즐이 주어졌을 때, 흩어짐 정도를 계산하여 출력한다.

 

문제 풀이 과정

1. 퍼즐을 풀었을 때의 위치를 리스트에 저장해놓는다.
2. 현재 상태의 퍼즐을 입력받는다.
3. 풀었을 때 퍼즐의 위치와 현재 상태 퍼즐의 위치가 다른 퍼즐이 있다면 그 퍼즐의 이름(알파벳)을 키로, 위치 튜플을 값으로 갖는 딕셔너리에 저장한다.
4. 흩어진 퍼즐의 위치와 원래 퍼즐의 위치를 행끼리, 열끼리 비교하여 그 차이를 합하여 각 퍼즐의 흩어짐 정도를 모두 더한다.
5. 흩어짐 정도를 출력한다.

 

코드 및 설명

puzzle = ['ABCD', 'EFGH', 'IJKL', 'MNO.']
puzzle2 = []  # 현재 퍼즐 상태
pos = {}  # 흩어진 퍼즐의 이름과 위치
cnt = 0  # 흩어짐 정도
for _ in range(4):
    puzzle2.append(input())

# 흩어진 퍼즐의 이름과 위치 저장
for i in range(4):
    for j in range(4):
        if puzzle[i][j] != puzzle2[i][j] and puzzle2[i][j] != '.':
            pos[puzzle2[i][j]] = (i, j)

# 흩어진 위치와 원래 위치의 거리 비교
for i in range(4):
    for j in range(4):
        if puzzle[i][j] in pos.keys():
            cnt += abs(pos[puzzle[i][j]][0]-i) + abs(pos[puzzle[i][j]][1]-j)

print(cnt)

---

BaekJoon 백준 3041 N-퍼즐 문제를 파이썬 python으로 풀어보았다. 난이도는 Bronze 브론즈 1이다.