백준 1600 [말이 되고픈 원숭이] 파이썬

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

 

막 덤비다가 깨졌다.

 

처음에는 방문을 고려하지 않고, 원숭이 이동과 말의 이동을 고려하여 처리를 하니 시간초과가 발생하였다.

 

# 백준 1600 말이 되고픈 원숭이
import sys
from collections import deque

dr=[0,0,1,-1]
dc=[1,-1,0,0]
horse_dr=[-2,-1,1,2,2,1,-1,-2]
horse_dc=[1,2,2,1,-1,-2,-2,-1]
success_flg=False

K=int(sys.stdin.readline())
col,row=map(int,sys.stdin.readline().split())
field = [[[0, ''] for _ in range(col)] for _ in range(row)]
visited= [[0 for _ in range(col)] for _ in range(row)]
for i in range(row):
    s=list(map(int,sys.stdin.readline().split()))
    for j in range(col):
        if s[j]==1:
            field[i][j][0]=-2
        else:
            field[i][j][0]=-1


q=deque()
q.append([0,0,K,'M'])
field[0][0]=[0,'M']
while q:
    r,c,k,kind=q.popleft()
    if r==(row-1) and c==(col-1):
        success_flg=True
        break
    for i in range(4):
        R=r+dr[i]
        C=c+dc[i]
        if 0<=R<row and 0<=C<col and (field[R][C][0]!=-2 and field[R][C][1]!='M'):
            field[R][C]=[field[r][c][0]+1,kind]
            q.append([R,C,k,kind])
            visited[R][C]=0
    if k>0:
        for i in range(8):
            R=r+horse_dr[i]
            C=c+horse_dc[i]
            if 0<=R<row and 0<=C<col and (field[R][C][0]==-1 or field[R][C][1]=='H') and visited[R][C]==0:
                field[R][C]=[field[r][c][0]+1,'H']
                visited[R][C]=1
                q.append([R,C,k-1,'H'])

if success_flg:
    print(field[row-1][col-1][0])
else:
    print(-1)

 

 

도저히 모르겠어서 이 문제는 포기했다.

GPT의 풀이를 보았는데, 엄청나다.. 

 

 

visited를 3차원 리스트로 생성하여 각 원소는 i,j,k(이동가능횟수)로 배열을 생성한다.

이렇게 되면 i,j가 같더라도 k값이 다르면 계속 탐색할 수 있으므로 문제가 없다.

import sys
from collections import deque

# 기본 방향(상하좌우)
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

# 말처럼 이동하는 방향 (8가지)
horse_dr = [-2, -1, 1, 2, 2, 1, -1, -2]
horse_dc = [1, 2, 2, 1, -1, -2, -2, -1]

# 입력 받기
K = int(sys.stdin.readline())  # 말처럼 이동할 수 있는 횟수
col, row = map(int, sys.stdin.readline().split())  # 가로(열), 세로(행) 크기

# 맵 정보 입력
field = [list(map(int, sys.stdin.readline().split())) for _ in range(row)]

# 방문 체크 배열 (3차원) → visited[row][col][말 이동 가능 횟수]
visited = [[[False] * (K + 1) for _ in range(col)] for _ in range(row)]

# BFS
q = deque()
q.append((0, 0, K, 0))  # (현재 행, 현재 열, 남은 말 이동 횟수, 이동 횟수)
visited[0][0][K] = True

while q:
    r, c, k, cnt = q.popleft()

    # 도착 지점에 도달하면 정답 출력 후 종료
    if r == row - 1 and c == col - 1:
        print(cnt)
        exit()

    # 1️⃣ 일반적인 이동 (상하좌우)
    for i in range(4):
        R, C = r + dr[i], c + dc[i]
        if 0 <= R < row and 0 <= C < col and not visited[R][C][k] and field[R][C] == 0:
            visited[R][C][k] = True
            q.append((R, C, k, cnt + 1))

    # 2️⃣ 말처럼 이동 (8방향)
    if k > 0:
        for i in range(8):
            R, C = r + horse_dr[i], c + horse_dc[i]
            if 0 <= R < row and 0 <= C < col and not visited[R][C][k - 1] and field[R][C] == 0:
                visited[R][C][k - 1] = True
                q.append((R, C, k - 1, cnt + 1))

# 도착할 수 없는 경우 -1 출력
print(-1)

갈 길이 멀다 흐흐