17198.md

백준 17198번 Bucket Brigade

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

---

코드 설명

• 처음 출발하는 곳의 좌표를 'B'가 있는 곳으로 잡았기 때문에 index 함수를 사용했다. -> map을 입력받을 때 시작좌표도 초기화시킴
• bfs를 통해 구했으며, 방문한 곳을 또 방문하지 않기 위해 'R'로 표시함으로써 중복방문 문제를 해결했다.
• 최단 경로를 구해야 하기 때문에 dis 라는 10 x 10 map을 하나 더 만들어 그곳에 거리를 표시화했다.
• dis에 거리값을 표시함으로써 가중치를 초기화할 수 있었고, 그에 'L'주변에 도달했을 경우 그 주변 좌표의 가중치를 리턴할 수 있었다.

소스코드

• 메모리 : 32404 KB
• 시간 : 84 ms

import sys
from collections import deque

def in_range(x,y):
	return 0 <= x < 10 and 0 <= y < 10

def bfs(x,y):
	q = deque()
	q.append((x,y))
	dxs, dys = [0,0,1,-1], [1,-1,0,0]
	
	while q:
		x, y = q.popleft()
		for dx, dy in zip(dxs, dys):
			nx, ny = x + dx, y + dy
			if in_range(nx,ny) and maps[nx][ny] != "R":
				if maps[nx][ny] == "L":
					return dis[x][y]
				maps[nx][ny] = "R"
				q.append((nx,ny))
				dis[nx][ny] = dis[x][y] + 1
	

maps = []
dis = [[0]*10 for _ in range(10)]
x, y = 0, 0
for i in range(10):
	arr = list(sys.stdin.readline().strip())
	maps.append(arr)
	if "B" in arr:
		x, y = i, arr.index("B")

print(bfs(x,y))