Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- BFS
- Python
- 이분 탐색
- boj
- JavaScript
- 모던 JavaScript 튜토리얼
- 브루트포스
- 구현
- 누적 합
- 해시 테이블
- SSAFY
- DFS
- 2357
- DP
- 세그먼트 트리
- 투 포인터
- 슬라이딩 윈도우
- 에라토스테네스의 체
- 애드 혹
- 싸피
- 맵
- 문자열
- 그리디
- 정렬
- 트리
- 13164
- 정수론
- 그래프
- 플로이드-워셜
- 수학
Archives
- Today
- Total
흙금이네 블로그
[BOJ] 9376 - 탈옥 (Python) 본문
아이디어
상근이가 있는 감옥 외부와 두 죄수가 있는 칸에서 각각 0-1 BFS로 탐색한다.
모든 칸에 대해 열어야 하는 최소 문 개수들을 구한 후, 세 사람이 만나는 칸의 문 개수 합의 최솟값을 구한다.
풀이
import sys
from collections import deque
input = sys.stdin.readline
delta = [(-1, 0), (0, 1), (1, 0), (0, -1)]
def solution():
def bfs(x, y):
visited = [[-1]*w for _ in range(h)]
visited[x][y] = 0
queue = deque([(x, y, 0)])
while queue:
r, c, cnt = queue.popleft()
for dr, dc in delta:
nr, nc = r+dr, c+dc
if h > nr >= 0 and w > nc >= 0:
if visited[nr][nc] == -1:
if board[nr][nc] == '#':
visited[nr][nc] = cnt+1
queue.append((nr, nc, cnt+1))
elif board[nr][nc] != '*':
visited[nr][nc] = cnt
queue.appendleft((nr, nc, cnt))
else:
visited[nr][nc] = -2
return visited
T = int(input())
for t in range(T):
h, w = map(int, input().split())
w += 2
board = [['.']*w]+[['.']+[*input().rstrip()]+['.'] for _ in range(h)]+[['.']*w]
h += 2
P = []
for r in range(1, h-1):
for c in range(1, w-1):
if board[r][c] == '$':
P.append((r, c))
visited1 = bfs(0, 0)
visited2 = bfs(P[0][0], P[0][1])
visited3 = bfs(P[1][0], P[1][1])
res = h*w
for r in range(h):
for c in range(w):
if visited1[r][c] >= 0 and visited2[r][c] >= 0 and visited3[r][c] >= 0:
door = visited1[r][c]+visited2[r][c]+visited3[r][c]
if board[r][c] == '#':
door -= 2
if door < res:
res = door
print(res)
solution()
'알고리즘' 카테고리의 다른 글
[BOJ] 1039 - 교환 (Python) (0) | 2023.04.11 |
---|---|
[BOJ] 6087 - 레이저 통신 (Python) (0) | 2023.04.11 |
[BOJ] 2933 - 미네랄 (Python) (0) | 2023.04.11 |
[BOJ] 11401 - 이항 계수 3 (Python) (0) | 2023.04.10 |
[BOJ] 3197 - 백조의 호수 (Python) (0) | 2023.04.10 |
Comments