[백준] 2206 벽부수고 이동하기, 1600 말이 되고픈 원숭이

1. 풀이

기본적인 bfs에 차원을 추가해서 응용되는 문제.

1). cL[i][j]는 시작점에서 i,j까지 갈 수 있는 최단거리가 저장된다.

2). bfs의 특성상 특정지점 (i,j)에 처음으로 방문한 순간이 최단거리가 된다. 즉 첫 방문에 최단거리임을 보장한다.

따라서 visited 리스트로 따로 방문여부를 관리할 필요가 없다 (방문했다면 해당자리 cL[i][j]에 원점에서 (i,j)까지의 거리가 적혀있을 것이고, 그것은 항상 최단거리이기 때문에)

3). 벽을 부수는횟수, 말 점프횟수가 제한되어있기 때문에 차원을 추가하여 해당 횟수를 관리한다.

 

2. 소스코드

(1) [백준]2206 벽부수고 이동하기

from collections import deque

N,M=map(int,input().split())
L=[]
for i in range(N):
    L.append(list(map(int,list(input()))))

q=deque()
q.append((0,0,0))
cL=[[[0,0] for i in range(M)] for j in range(N)]

cL[0][0][0]=1
dr=[0,0,1,-1]
dc=[1,-1,0,0]


while(q):
    r,c,h=q.popleft()
    for k in range(4):
        tempR=r+dr[k]
        tempC=c+dc[k]
        if 0<=tempR<N and 0<=tempC<M:
            if L[tempR][tempC]==0 and cL[tempR][tempC][h]==0:
                cL[tempR][tempC][h]=cL[r][c][h]+1
                q.append((tempR,tempC,h))
            elif L[tempR][tempC]==1 and h==0 and cL[tempR][tempC][1]==0:
                cL[tempR][tempC][1]=cL[r][c][0]+1
                q.append((tempR,tempC,1))


if cL[N-1][M-1][0]==0 and cL[N-1][M-1][1]==0:
    print(-1)
elif cL[N-1][M-1][0]==0:
    print(cL[N-1][M-1][1])
elif cL[N-1][M-1][1]==0:
    print(cL[N-1][M-1][0])
else:
    print(min(cL[N-1][M-1][0],cL[N-1][M-1][1]))

 

(2) [백준]1600 말이 되고픈 원숭이

from collections import deque

K=int(input())
W,H=map(int,input().split())
L=[]
for i in range(H):
    L.append(list(map(int,input().split())))

dR=[0,0,-1,1]
dC=[1,-1,0,0]
dhR=[-1,-2,-2,-1,1,2,2,1]
dhC=[-2,-1,1,2,2,1,-1,-2]

cL=[[[0 for k in range(K+1)] for j in range(W)] for i in range(H)]
for i in range(K+1):
    cL[0][0][i]=1

ans=0
q=deque([[0,0,0]])
while(q):
    temp=q.popleft()
    r=temp[0]
    c=temp[1]
    h=temp[2]
    if r==H-1 and c==W-1:
        ans=cL[r][c][h]
        break

    # 인접칸이동
    for d in range(4):
        tempR=r+dR[d]
        tempC=c+dC[d]
        if 0<=tempR<H and 0<=tempC<W and L[tempR][tempC]==0 and cL[tempR][tempC][h]==0:
            cL[tempR][tempC][h]=cL[r][c][h]+1
            q.append([tempR,tempC,h])
    # 말뛰기
    if h!=K:
        for k in range(8):
            tempR=r+dhR[k]
            tempC=c+dhC[k]
            if 0<=tempR<H and 0<=tempC<W and L[tempR][tempC]==0 and cL[tempR][tempC][h+1]==0:
                cL[tempR][tempC][h+1]=cL[r][c][h]+1
                q.append([tempR,tempC,h+1])

'''
#값확인
for i in range(H):
    print(cL[i])
'''

print(ans-1)