문제 링크

설계

항상 풀어왔던 BFS 문제이지만 조건이 조금 신박했다.

위와 같은 상황에서 "텔레포트"를 한다는 것.

여담이지만 백준의 치즈 문제의 경우 장애물을 없애는 문제였다.

main

if __name__ == '__main__':
	R,C,K = map(int,input().split())
	graph = [[0]*C for _ in range(R)]
	for i in range(R):
		tmp = input()
		for j in range(len(tmp)):
			graph[i][j] = int(tmp[j])
	
	print(bfs(graph,R-1,C-1,K))

입력 조건을 받고 BFS를 돌린다.

bfs

def bfs(graph,tx,ty,K):
	q = deque([(0,0,0,K)])
	visited = defaultdict(set)
	visited[K].add((0,0))
	dx = [1,-1,0,0]
	dy = [0,0,1,-1]
	
	while q:
		x,y,cnt,mp = q.popleft()
		
		if (x,y) == (tx,ty):
			return cnt
		
		for i in range(4):
			nx = x+dx[i]
			ny = y+dy[i]
			
			if 0<=nx<R and 0<=ny<C and (nx,ny) not in visited[mp]:
				if graph[nx][ny] == 1:
					if mp >= 10:
						jx,jy = nx+dx[i], ny+dy[i]
						if 0<=jx<R and 0<=jy<C and graph[jx][jy] == 0:
							q.append((jx,jy,cnt+1,mp-10))
							visited[mp-10].add((jx,jy))
				else:
					q.append((nx,ny,cnt+1,mp))
					visited[mp].add((nx,ny))
	return -1

일반적인 BFS 코드에서 변경 사항이 있다면 visited를 딕셔너리로 설계했다는 점이다.

왜???

visited를 배열로 만들었을 때 생기는 문제점은 다음과 같다.

파란색이 마나를 아직 소모하지 않은 경우고
초록색이 마나를 소모하여 나무를 넘은 경우다.

그림에서 알 수 있듯이 초록 루트가 (3,2) 위치에 먼저 도달하여
방문 처리를 하였고 때문에 파란 루트가 (3,2)에 도달하지 못 한다.

그러나 파란 루트는 아직 마나를 쓰지 않았기 때문에 나무를 넘어 목적지까지 도달할 수 있지만 이미 처리된 방문 표시 때문에 -1을 반환하게 된다.

따라서 이를 딕셔너리를 활용하여 다음과 같이 수정할 수 있다.

파란 루트와 초록 루트의 방문 배열을 따로 생성하여 파란 루트도 지나갈 수 있도록 했다.

즉, 잔여 마나를 key값으로 visited 집합을 만들었다.

🚨 value를 리스트로 만드니 시간 초과가 발생했다. set으로 만들 것! 🚨

전체 코드

from collections import deque,defaultdict

def bfs(graph,tx,ty,K):
	q = deque([(0,0,0,K)])
	visited = defaultdict(set)
	visited[K].add((0,0))
	dx = [1,-1,0,0]
	dy = [0,0,1,-1]
	
	while q:
		x,y,cnt,mp = q.popleft()
		
		if (x,y) == (tx,ty):
			return cnt
		
		for i in range(4):
			nx = x+dx[i]
			ny = y+dy[i]
			
			if 0<=nx<R and 0<=ny<C and (nx,ny) not in visited[mp]:
				if graph[nx][ny] == 1:
					if mp >= 10:
						jx,jy = nx+dx[i], ny+dy[i]
						if 0<=jx<R and 0<=jy<C and graph[jx][jy] == 0:
							q.append((jx,jy,cnt+1,mp-10))
							visited[mp-10].add((jx,jy))
				else:
					q.append((nx,ny,cnt+1,mp))
					visited[mp].add((nx,ny))
	return -1

if __name__ == '__main__':
	R,C,K = map(int,input().split())
	graph = [[0]*C for _ in range(R)]
	for i in range(R):
		tmp = input()
		for j in range(len(tmp)):
			graph[i][j] = int(tmp[j])
	
	print(bfs(graph,R-1,C-1,K))