2589

날짜 : 2023. 03. 10

사용 언어 : python

 

문제

 

 

코드

import copy
import sys
from collections import deque

m, n = map(int, sys.stdin.readline().split())  # 세로, 가로
world = list()
visited = [[True] * n for i in range(m)]  # 방문처리용
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
res = 0
for _ in range(m): world.append(sys.stdin.readline().rstrip())


def bfs(r, c):
    q = deque()
    cnt = 0  # 이동횟수
    q.append([r, c])
    v = [[0] * n for i in range(m)]  # 방문처리용
    v[r][c] = 1
    while q:
        x, y = q.popleft()
        for i in range(4):  # 인접 이동
            nx = x + dx[i]
            ny = y + dy[i]
            if nx in range(m) and ny in range(n):  # 범위 포함
                if world[nx][ny] == "L" and v[nx][ny] == 0:  # 방문하지 않았고 육지인 경우
                    v[nx][ny] = v[x][y] + 1  # 방문처리
                    cnt = max(cnt, v[nx][ny])  # 이동횟수 증가
                    q.append([nx, ny])  # 큐에 삽입
    """for i in v:
        print(i)
    print()"""
    return cnt-1


for i in range(m):
    for j in range(n):
        if world[i][j] == "L":  # 육지인 경우
            res = max(res, bfs(i, j))

print(res)

 

오답코드

import copy
import sys
from collections import deque

m, n = map(int, sys.stdin.readline().split())  # 세로, 가로
world = list()
visited = [[True] * n for i in range(m)]  # 방문처리용
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
res = 0
for _ in range(m): world.append(sys.stdin.readline().rstrip())

for i in range(m):
    for j in range(n):
        if world[i][j] == "L": visited[i][j] = False  # 육지 -> 미방문처리


def bfs(r, c):
    q = deque()
    cnt = 0  # 이동횟수
    q.append([r, c])
    v = [[True] * n for i in range(m)]  # 방문처리용
    for i in range(m):
        for j in range(n):
            if world[i][j] == "L": v[i][j] = False  # 육지 -> 미방문
    v[r][c] = True
    while q:
        x, y = q.popleft()
        for i in range(4):  # 인접 이동
            nx = x + dx[i]
            ny = y + dy[i]
            if nx in range(m) and ny in range(n):  # 범위 포함
                if world[nx][ny] == "L" and not v[nx][ny]:  # 방문하지 않았고 육지인 경우
                    v[nx][ny] = True  # 방문처리
                    cnt += 1  # 이동횟수 증가(탐색할 때마다 증가한다)
                    q.append([nx, ny])  # 큐에 삽입
    """for i in v:
        print(i)
    print()"""
    return cnt-1


for i in range(m):
    for j in range(n):
        if world[i][j] == "L":  # 육지인 경우
            res = max(res, bfs(i, j))

print(res)

 

풀이

- 육지인 경우 각 섬들을 탐색하는 bfs를 실행한다.

- bfs 함수에서는 각 섬의 이동거리를 계산 후 그 최대값을 출력하는 방식으로 탐색한다.

 

 

알게된 점

- 이 문제에서의 키포인트는 방문처리를 하되 방식을 단순 True / False가 아니라 각 섬 이동거리를 해당 리스트에 최신화시키면서 진행하는 것이었다.

- 오답코드를 보면 True, False로 진행하는 것으로 탐색했는데 해당 경우에는 연결된 모든 육지를 탐색하며, 탐색할 때마다 카운트가 1씩 증가한다.

- 그렇기 때문에 이 문제에서는 방문처리를 True, False가 아닌 이동거리로 설정하는 것이 해결하는데 더 효율적인 방법이라고 할 수 있다.

0(바다)으로 설정하면 탐색 안함

 

 

참고 사이트

- https://velog.io/@bye9/백준파이썬-2589-보물섬