문제 링크
문제 풀이
- 이 문제는 각 육지에서 다른 육지로의 거리 중 최대 거리를 구하는 문제이다.
- 먼저, 육지(L)인 경우, 너비 우선 탐색을 진행할 수 있도록 한다(for문). 너비 우선 탐색을 진행한 후에는 결과값(res)을 기존의 값과 비교하여 더 큰 값을 저장하도록 한다.
- 너비 우선 탐색을 진행할 때에는 현재 육지에서 다른 육지와의 거리를 구할 수 있도록 카운트값(c)를 같이 큐에 넣어 진행한다. 큐가 빌 때까지 진행하는데, 마지막에 들어간 값이 가장 거리가 먼 육지가 되므로 최종적으로는 카운트값을 반환해야 한다.
- 모든 육지에 대해서 너비 우선 탐색을 진행하면, 최대 거리를 구할 수 있다.
전체 코드
import sys
from collections import deque
def bfs(x, y, c):
queue = deque()
queue.append((x, y, c))
visited[x][y] = True
while queue:
x, y, c = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if not visited[nx][ny] and arr[nx][ny] == "L":
visited[nx][ny] = True
queue.append((nx, ny, c+1))
return c
n, m = map(int, sys.stdin.readline().split())
arr = [list(sys.stdin.readline().strip()) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
res = 0
for i in range(n):
for j in range(m):
if arr[i][j] == "L":
visited = [[False] * m for _ in range(n)]
res = max(res, bfs(i, j, 0))
print(res)
반응형
'Coding Test > BOJ' 카테고리의 다른 글
[백준/Python] 1021 회전하는 큐 (0) | 2024.02.25 |
---|---|
[백준/Python] 16564 히오스 프로게이머 (0) | 2024.02.24 |
[백준/Python] 13164 행복 유치원 (0) | 2024.02.22 |
[백준/Python] 12865 평범한 배낭 (0) | 2024.02.20 |
[백준/Python] 2564 경비원 (0) | 2024.02.19 |