[백준] 2589 보물섬

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

문제를 처음 접했을때, 트리의 지름을 구하는 원리를 이용하였습니다.

여러 육지로 이루어진 하나의 대륙(덩어리)의 한 좌표에서 가장 멀리 있는 좌표를 구한 이후 다시 그 좌표에서 가장 멀리 있는 값을 구하였습니다.

 

그러나 육지가 트리와 같은 형태를 이루지 않는 경우가 존재하였습니다.

예를 들어 하나의 노드를 선택하여 루트노드로 지정하였다면 다른 노드들은 자식 노드가 되는데, 특정 경우에 어떤 좌표를 루트노드로 지정하였는데 리프노드가 다시 루트노드와 이어지는 순환하는 형태를 나타냈습니다.

이러한 경우에 올바른 정답을 찾을 수 없었습니다.

 

이후 모든 좌표들을 한번씩 BFS를 이용하여 탐색하며 가장 먼 거리를 구하였고, 그 거리들 중 가장 긴 값을 계속해서 갱신하였습니다.

2) 알고리즘

• 완전 탐색
• BFS

3) 풀이 코드

사용 언어 - Python

아래의 답은 pypy3 로 통과하였으나, 60% 대에서 python3 로는 시간초과가 발생하였습니다.

import sys
from collections import deque
sys.stdin = open('input.txt')

dr = [-1, 0, 1, 0]      # 위 오른쪽 아래 왼쪽
dc = [0, 1, 0, -1]

def solution(y, x):
    q = deque([(y, x)])
    visited = [[-1] * C for _ in range(R)]      # 시작점에서 특정 지점까지 거리
    visited[y][x] = 0                           # 시작점은 거리 0으로 할당

    while q:
        node = q.popleft()          # 육지 좌표
        for k in range(4):
            r = node[0] + dr[k]     # 다음 탐색할 좌표
            c = node[1] + dc[k]

            if 0 <= r < R and 0 <= c < C and visited[r][c] == -1 and board[r][c] == 'L':
                # 다음 좌표가 범위 내이고 아직 방문하지 않았으며, 육지인 경우
                visited[r][c] = visited[node[0]][node[1]] + 1       # 해당 위치까지 거리 기록
                q.append((r, c))

    return visited[node[0]][node[1]]                                # 가장 먼 육지까지 거리 반환


R, C = map(int, sys.stdin.readline().split())                       # 세로, 가로
board = [list(sys.stdin.readline().rstrip()) for _ in range(R)]     # 입력 정보
answer = 0

for i in range(R):
    for j in range(C):
        if board[i][j] == 'L':              # 2차원 배열을 순환하며 육지인 경우에
            ans = solution(i, j)            # 현재 좌표에서 다른 육지로 가는 가장 긴 거리
            answer = max(ans, answer)       # 이전 거리와 현재 값 중 가장 긴 거리를 저장

print(answer)

---

🔗 문제 링크

- https://www.acmicpc.net/problem/2589

2589번: 보물섬

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다