[#2589] 보물섬

RookieAND·2022년 6월 17일

BFS 백준 브루트포스 코테

BaekJoon

목록 보기

20/42

❓ Question

https://www.acmicpc.net/problem/2630

📖 Before Start

BFS 탐색을 기반으로 브루트포스를 가미하여 풀어야 하는 문제다.

이번 문제는 BFS 탐색과 완전 탐색을 적절히 사용하여 풀어야 하는 문제였다.
처음 설계한 알고리즘이 시간 초과를 일으켜 어떤 점이 잘못되었는지를 파악하고,
개선된 방법을 고안하여 푼 결과 마침내 최종 solved 처리를 받은 문제였다.

✒️ Design Algorithm

각 육지의 좌표 별로 이동 거리의 최댓값을 먼저 도출해야 한다.

N X M 크기의 이차원 배열 안에 육지 L 과 바다 W 가 골고루 분포되어 있다.
탐색이 가능한 곳은 오직 육지 L 뿐이며, 최단 거리로 이동할 경우의 최댓값을 구해야 한다.

처음 문제를 풀었을 땐 모든 육지 좌표를 tuple 형태로 가공하여 하나의 List 에 저장하였고,
이후 조합 (Combination) 을 통해 육지 좌표 2개를 추출하여 좌표 간 최단 거리를 계산하였다.

두 좌표를 추출하고, 최단 거리의 최댓값을 구하는 과정은 아래와 같다.

육지 좌표를 담은 land_locs 에서 두 개의 좌표를 조합을 통해 선별한다.
이후 BFS 탐색을 통해 두 좌표 간의 최단 거리 를 구하고, 기존의 값과 대조한다.

💻 Making Own Code

❌ Wrong Code

import sys
from itertools import combinations as comb
from collections import deque

read = sys.stdin.readline
N, M = map(int, read().split())
matrix, land_locs = [], []
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]

for row in range(N):
    mat_row = list(read().strip())
    for col in range(M):
        if mat_row[col] == 'L':
            land_locs.append((row, col))
    matrix.append(mat_row)

# 두 좌표를 tuple로 받는 bfs 탐색 함수 선언.
def bfs(f_loc, s_loc):
    # 방문 여부를 판별하는 이차원 배열을 새롭게 생성.
    visited = [[-1] * M for _ in range(N)]
    # 탐색을 시작할 좌표인 f_loc의 경우 값을 0으로 초기화.
    visited[f_loc[0]][f_loc[1]] = 0
    queue = deque([f_loc])
    while queue:
        y, x = queue.popleft()
        for direct in direction:
            ny, nx = y + direct[0], x + direct[1]
            # 만약 탐색된 좌표가 유효 범위 이내이며, 아직 미방문된 곳인지 판별.
            if 0 <= ny < N and 0 <= nx < M:
                if visited[ny][nx] == -1 and matrix[ny][nx] == 'L':
                    visited[ny][nx] = visited[y][x] + 1
                    queue.append((ny, nx))

    # 탐색을 종료할 좌표인 s_loc 좌표에 든 값을 return
    return visited[s_loc[0]][s_loc[1]]

result = 0
# 육지인 좌표 목록 중에서 2개를 추출해야 함.
for land_loc in comb(land_locs, 2):
    first_loc, second_loc = land_loc
    # 기존의 값과 새로운 값 중에서 더 큰 값을 결과에 업데이트.
    result = max(result, bfs(first_loc, second_loc))

print(result)

나쁘지 않은 시도였지만, 시간 초과가 발생하여 풀이에는 실패했다.

설계 과정에서 틀린 점은 없었으나, 문제는 조합으로 선별할 수 있는 경우의 수가 너무 많았다.
최대 50 X 50 까지 커질 수 있는 2차원 공간에서, 두 좌표를 조합으로 선별한다면... 끔찍하다.

결국 문제를 푸는 접근 방식을 살짝 수정하였는데, 개선된 방안은 아래와 같다.

육지 좌표를 모아둔 List 에서 좌표 한 개를 추출하여 BFS 탐색 을 시행한다.
탐색을 진행하면서 각 좌표 간의 이동 거리 중 최댓값을 실시간으로 업데이트 한다.
이후 최종적으로 나온 최댓값을 return 하고, 기존의 최단 거리와 대조를 진행한다.

텍스트로 쓰려니 설명이 조금 빈약한데, 하단의 코드를 보면 이해가 더 쉬울 것이다.

✅ Correct Code

import sys
from collections import deque

read = sys.stdin.readline
N, M = map(int, read().split())
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]

# 보물 지도와 육지의 좌표를 추출하는 과정.
matrix, land_locs = [], []
for row in range(N):
    mat_row = list(read().strip())
    for col in range(M):
        if mat_row[col] == 'L':
            land_locs.append((row, col))
    matrix.append(mat_row)


# 두 좌표를 tuple로 받는 bfs 탐색 함수 선언.
def bfs(y, x):
    # 방문 여부를 판별하는 이차원 배열을 새롭게 생성.
    visited = [[-1] * M for _ in range(N)]
    visited[y][x] = 0
    queue, distance = deque([(y, x)]), 0
    while queue:
        ny, nx = queue.popleft()
        distance = max(visited[ny][nx], distance)
        for direct in direction:
            my, mx = ny + direct[0], nx + direct[1]
            # 만약 탐색된 좌표가 유효 범위 이내이며, 아직 미방문된 곳인지 판별.
            if 0 <= my < N and 0 <= mx < M:
                if visited[my][mx] == -1 and matrix[my][mx] == 'L':
                    queue.append((my, mx))
                    visited[my][mx] = visited[ny][nx] + 1

    return distance


result = 0
# 모든 육지의 좌표를 하나씩 순화하며 나온 최단 거리 비교
for land_loc in land_locs:
    loc_y, loc_x = land_loc
    result = max(result, bfs(loc_y, loc_x))

print(result)

메모리 초과, 시간 초과의 경우 결국 얼마나 더 실행 횟수와 조건을 간소화 시키느냐가 관건이라 생각한다.
이번 문제도 조합으로 문제를 풀었다가, 너무나 많은 경우의 수를 판별하는 과정에서 시간 초과가 일어났는데,
좌표를 하나만 체크하는 방식으로 알고리즘을 수정하니 단박에 solved 처리가 되었다.