Jin의 일상

BFS에 조금 변형을 줘서 풀 수 있는 문제다.

일반적으로 BFS는 큐 자료구조를 통해 풀 수 있다.

큐는 선입 선출(FIFO)이므로, 기본 컨셉에 따르면 맨 뒤에 새로운 값을 넣어준 뒤 맨 앞에서 값을 빼내야 한다.

그런데 이 문제의 특정 조건에서는 큐의 맨 앞에 새로운 값을 넣어준다.

이 방법을 통해 우선적으로 탐색되어야 할 좌표에 가중치를 부여한 것이다.

어쨌든, 인풋되는 방식만 다를 뿐 알고리즘은 똑같이 작동한다.

나는 두 가지 방식으로 알고스팟 문제를 풀었는데, 앞에서 설명한 것이 A 방식이다.

B 방식은 다음 좌표의 값이 현재 좌표의 값보다 작다면 이동하는 방식을 취하고 있다.

전형적인 BFS에 조건을 하나 추가한 것이다.  하지만 채점의 63%정도 구간에서 메모리 초과로 테스트를 통과하지 못했다. 그래도 테스트 케이스는 모두 통과할 것으로 생각된다.

메모리 초과한 원인을 분석하기 위해 BFS 진행 간 A와 B 방식의 Queue 값을 출력했다.

A 코드는 우선적으로 탐색해야 할 좌표에 가중치를 부여했으므로, 불필요한 탐색이 깊게 진행되지 않았다. 

반면에 B 코드는 이전에 4번의 벽을 부수고 이동했는데, 이번에 3번 벽을 이동한 경로가 발견됐다면 3으로 갱신하고 다음 번에 1번만 벽을 부수어도 된다면 다시 갱신하고,. ..... 이렇게 반복해야 한다. 따라서 불필요한 탐색이 깊게 진행된다.

그래서 Queue에 저장될 좌표도 많아질 수 밖에 없던 것이다.

A 코드

# A 코드: 좌표의 상태에 따라 가중치를 부여함 

import sys
from collections import deque

INPUT = sys.stdin.readline
DIRECTION = ((0, 1), (0, -1), (1, 0), (-1, 0))


def solution():
    m, n = map(int, INPUT().split())
    board = [list(map(int, INPUT().rstrip())) for _ in range(n)]
    visited = [[-1] * m for _ in range(n)]

    visited[0][0] = 0
    q = deque([[0, 0]])
    while q:
        x, y = q.popleft()

        for i in range(4):
            next_x = x + DIRECTION[i][0]
            next_y = y + DIRECTION[i][1]

            if (0 > next_x or next_x >= m) or (0 > next_y or next_y >= n):
                continue

            if visited[next_y][next_x] != -1:
                continue

            if board[next_y][next_x] == 0:
                visited[next_y][next_x] = visited[y][x]
                q.appendleft([next_x, next_y])
            else:
                visited[next_y][next_x] = visited[y][x] + 1
                q.append([next_x, next_y])
    return visited[n-1][m-1]
print(solution())

B 코드 

# B 코드: 좌표별 상태에 따라 가중치를 부여하지 않음. (메모리 초과)

import sys
from collections import deque

INPUT = sys.stdin.readline
MAX = 9999999
DIRECTION = ((0, 1), (0, -1), (1, 0), (-1, 0))


def solution():
    m, n = map(int, INPUT().split())
    board = [list(map(int, INPUT().rstrip())) for _ in range(n)]
    visited = [[MAX] * m for _ in range(n)]

    visited[0][0] = 0
    q = deque([[0, 0]])
    while q:
        x, y = q.popleft()

        for i in range(4):
            next_x = x + DIRECTION[i][0]
            next_y = y + DIRECTION[i][1]

            if (0 > next_x or next_x >= m) or (0 > next_y or next_y >= n):
                continue

            if visited[next_y][next_x] <= visited[y][x]:
                continue

            if board[next_y][next_x] == 0:
                visited[next_y][next_x] = visited[y][x]
                q.appendleft([next_x, next_y])
            else:
                visited[next_y][next_x] = visited[y][x] + 1
                q.append([next_x, next_y])
    return visited[n-1][m-1]
print(solution())

import sys
import copy
from collections import deque

# sys.stdin = open('input.txt', 'r')

INPUT = sys.stdin.readline
DIRECTION = ((0, 1), (0, -1), (1, 0), (-1, 0))
N, M = map(int, INPUT().split())


def count_safe_area(board):
    cnt = 0
    for y in range(N):
        for x in range(M):
            if board[y][x] == 0:
                cnt += 1
    return cnt


def spread_virus(board, virus_zone):
    q = deque(virus_zone)
    while q:
        x, y = q.popleft()

        for i in range(4):
            next_x = x + DIRECTION[i][0]
            next_y = y + DIRECTION[i][1]

            if 0 <= next_x < M and 0 <= next_y < N:
                if board[next_y][next_x] == 0:
                    board[next_y][next_x] = 2
                    q.append([next_x, next_y])


def find_all_cases(board, safe_zone):
    length = len(safe_zone)

    for i in range(length):
        for j in range(i + 1, length):
            for k in range(j + 1, length):
                tmp_board = copy.deepcopy(board)

                tmp_board[safe_zone[i][1]][safe_zone[i][0]] = 1
                tmp_board[safe_zone[j][1]][safe_zone[j][0]] = 1
                tmp_board[safe_zone[k][1]][safe_zone[k][0]] = 1
                yield tmp_board


def solution():
    """ 벽(1) 세 개를 세워서 바이러스(2)의 확산을 최대한 막습니다. 이 때, 안전 영역(0)의 최대 개수를 출력합니다.

    * 벽 세 개를 세울 수 있는 모든 경우의 수에 대해 아래 알고리즘을 단계별로 수행합니다.
     (1) 벽 세 개를 세울 수 있는 케이스를 생성합니다.
     (2) 바이러스를 퍼뜨립니다.
     (3) 바이러스를 퍼뜨렸을 때 안전 영역의 크기를 구합니다.
     (4) 최대 안전 영역의 크기로 갱신합니다.
     """
    board = [list(map(int, INPUT().split())) for _ in range(N)]
    safe_zone = []
    virus_zone = []
    res = -1

    for y in range(N):
        for x in range(M):
            if board[y][x] == 0:
                safe_zone.append([x, y])
            if board[y][x] == 2:
                virus_zone.append([x, y])

    # 핵심 알고리즘
    for case in find_all_cases(board, safe_zone):
        spread_virus(case, virus_zone)
        res = max(res, count_safe_area(case))
    return res
print(solution())

문제

1. x, y, z 방향으로 BFS를 실행하는 문제다.

2. x, y는 격자무늬 상자 안에 있는 토마토의 좌표를 의미하며, z는 겹쳐 올린 상자의 층을 뜻한다.

3. 상자 안에 있는 토마토는 0, 1, -1의 상태를 가진다. 

(0 : 토마토가 익지 않았다,  1 : 토마토가 익었다,  -1 : 토마토가 존재하지 않는다)

4. 토마토는 매일 "상/하/좌/우/위/아래" 방향으로 전염되어 익는다.

5. 토마토가 익는 데 걸리는 최소 일 수을 출력한다. 

 - 처음부터 모든 토마토가 익었으면 0을 출력한다. 

 - 모든 토마토를 익히지 못한다면 -1을 출력한다. 

알고리즘

1. 3차원 배열에서의 BFS만 구현하면 된다. (기본 2차원 배열에서 배열을 하나 더 추가한 것이다.)

1. 익은 토마토의 좌표를 리스트에 담는다.

2. 익은 토마토를 중심으로 상/하/좌/우/위/아래로 좌표를 이동시킨다.

3. 이동한 좌표가 좌표평면에서 벗어나지 않는다면 계속 진행한다.

4. 이동 전 익은 토마토의 좌표의 값에 1을 더하여 이동 후의 좌표 평면에 1을 더해준다. (매일 주변에 있는 토마토가 익으므로, 좌표평면에 존재하는 값은 "지난 일수"를 의미 한다.)

5. 좌표를 이동함으로써 익게 된 토마토의 좌표를 리스트에 담는다.

6. x, y, z 방향으로 3중 반복문을 실행하여 토마토가 전부 익었는지 확인한다.

 - 모두 익지 않았다면 -1을 출력하고 프로그램을 종료한다. 

7. 최대 값(mx)을 1로 초기화한다.

 - 문제 조건에서 처음부터 토마토가 모두 익었으면 0을 출력하라고 했다.

8. x, y, z 방향으로 3중 반복문을 실행하여, mx와 비교하며 좌표 평면에서 가장 큰 수(익는데 걸린 일수)를 찾는다.

9. mx - 1을 해서 정답을 출력한다.

  - 시작 시에 좌표평면의 값이 1이므로, 익는데 걸린 시간에 포함시키지 않는다.

코드

import sys
from collections import deque
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def BFS():
    while queue:
        x, y, z = queue.popleft()
        for dx, dy, dz in mv:
            xx = x + dx
            yy = y + dy
            zz = z + dz
            if 0 <= xx < col and 0 <= yy < row and 0 <= zz < height and board[zz][yy][xx] == 0:
                board[zz][yy][xx] = board[z][y][x] + 1
                queue.append([xx, yy, zz])

if __name__ == '__main__':
    col, row, height = map(int, input().split())
    board = [[list(map(int, input().split())) for _ in range(row)] for _ in range(height)]
    mv = ((1, 0, 0), (-1, 0, 0), (0, 1, 0), (0, -1, 0), (0, 0, 1), (0, 0, -1))

    # 익은 것의 좌표를 찾는다.
    queue = deque()
    for y in range(row):
        for x in range(col):
            for z in range(height):
                if board[z][y][x] == 1:
                    queue.append([x, y, z])

    BFS()
    # 모두 다 익었는지 확인한다.
    for y in range(row):
        for x in range(col):
            for z in range(height):
                if board[z][y][x] == 0:
                    print(-1)
                    sys.exit()

    # 걸린 일수를 출력한다.
    mx = 1
    for z in range(height):
        for y in range(row):
            mx = max(mx, max(board[z][y]))
    print(mx-1)