[파이썬] 백준 2314 : 이세계 게임 (골드3)

[파이썬] 백준 2314 : 이세계 게임 (골드3)

2314번: 이세계 게임

---

문제

---

풀이

0. 방향성 생각

• 현재 상태를 tuple, str으로 변환해서 set에 저장하는 문제

1. 입력

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

arr = [list(input()) for _ in range(4)]

goal = ''
while True:
    s = input()
    if s:
        goal += s
        break

for _ in range(3):
    goal += input()

def to_string(array):
    string = ''
    for row in array:
        string += ''.join(row)
    return string

• 공백 받다가, 공백아니면 탈출
• 2차원 배열을 string으로 변환하는 함수도 하나 정의

2. BFS

dire = [(1,0),(0,1),(-1,0),(0,-1)]
visit = set()
visit.add
q = deque([(0,arr)])
while q:
    t,cur = q.popleft()
    
    if to_string(cur) == goal:
        print(t)
        break
    
    for y in range(4):
        for x in range(4):
            for dx,dy in dire:
                nx,ny = x+dx, y+dy
                if 0<=nx<4 and 0<=ny<4 and cur[ny][nx] != cur[y][x]:
                    
                    nxt = [row[:] for row in cur]
                    nxt[ny][nx],nxt[y][x] = nxt[y][x],nxt[ny][nx]
                    nxt_str = to_string(nxt)
                    if nxt_str not in visit:
                        visit.add(nxt_str)
                        q.append((t+1,nxt))

• 현재 배열 cur을 temp로 복사한 후, nxt를 변환시켜서 visit에 없으면 새로 추가해주기

 

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

arr = [list(input()) for _ in range(4)]

goal = ''
while True:
    s = input()
    if s:
        goal += s
        break

for _ in range(3):
    goal += input()

def to_string(array):
    string = ''
    for row in array:
        string += ''.join(row)
    return string

dire = [(1,0),(0,1),(-1,0),(0,-1)]
visit = set()
visit.add
q = deque([(0,arr)])
while q:
    t,cur = q.popleft()
    
    if to_string(cur) == goal:
        print(t)
        break
    
    for y in range(4):
        for x in range(4):
            for dx,dy in dire:
                nx,ny = x+dx, y+dy
                if 0<=nx<4 and 0<=ny<4 and cur[ny][nx] != cur[y][x]:
                    
                    nxt = [row[:] for row in cur]
                    nxt[ny][nx],nxt[y][x] = nxt[y][x],nxt[ny][nx]
                    nxt_str = to_string(nxt)
                    if nxt_str not in visit:
                        visit.add(nxt_str)
                        q.append((t+1,nxt))

 

코멘트

웰노운이라 그런가 골3치고 매우쉬운

1525번: 퍼즐 (acmicpc.net)

1327번: 소트 게임 (acmicpc.net)

이거랑 비슷한 문제.