✅문제
✅문제 풀이
외부에서 BFS를 한번 돌리고 죄수 2명을 기준으로 BFS를 한번씩 지나간 문의 수를 카운트해서 합치면 답이 나온다.
1. 외부에서 BFS를 돌리기 위해서 배열 바깥에 "." 문자열을 추가해서 실행시킨다.
ex) 그럼 위에서 첫번째 테스트케이스의 경우 아래와 같이 배열이 실행된다.
2. 최단 경로는 3개의 배열의 위치가 같고 값이 같은 곳이다.(한 지점에 3개의 장소에서 최단거리로 도착했다는 의미)
3. 3경로가 같이 지나간 값을 전부 더해서 2번 더 중복됐으니 -2를 해주면 결과값이 나온다.
✅Code
from collections import deque
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def bfs(a, x, y):
n = len(a)
m = len(a[0])
dist = [[-1]*m for _ in range(n)]
q = deque()
q.append((x,y))
dist[x][y] = 0
while q:
x,y = q.popleft()
for k in range(4):
nx,ny = x+dx[k], y+dy[k]
if 0 <= nx < n and 0 <= ny < m and dist[nx][ny] == -1 and a[nx][ny] != '*':
if a[nx][ny] == '#':
dist[nx][ny] = dist[x][y] + 1
q.append((nx,ny))
else:
dist[nx][ny] = dist[x][y]
q.appendleft((nx,ny))
return dist
t = int(input())
for _ in range(t):
n,m = map(int,input().split())
a = ['.'+input()+'.' for _ in range(n)]
n += 2
m += 2
a = ['.'*m] + a + ['.'*m]
d0 = bfs(a, 0, 0)
x1=y1=x2=y2=-1
for i in range(n):
for j in range(m):
if a[i][j] == '$':
if x1 == -1:
x1,y1 = i,j
else:
x2,y2 = i,j
d1 = bfs(a,x1,y1)
d2 = bfs(a,x2,y2)
ans = n*m
for i in range(n):
for j in range(m):
if a[i][j] == '*':
continue
if d0[i][j] == -1 or d1[i][j] == -1 or d2[i][j] == -1:
continue
cur = d0[i][j] + d1[i][j] + d2[i][j]
if a[i][j] == '#':
cur -= 2
ans = min(ans,cur)
print(ans)
'알고리즘 > BFS, DFS' 카테고리의 다른 글
[Java] 백준 2667번 단지번호붙이기 풀이 (0) | 2024.07.31 |
---|---|
[Java] 백준 1707번 이분 그래프 풀이 (0) | 2024.07.30 |
[Java] 백준11724번 연결요소의 개수 풀이 (0) | 2024.07.30 |
[Java]백준 1260번 DFS와 BFS 풀이 (1) | 2024.07.30 |
[백준] 9328번 : 열쇠 풀이(python) (1) | 2023.10.13 |