17485. 진우의 달 여행

백준 / 17484. 진우의 달 여행 (Small) / 실버 3
백준 / 17485. 진우의 달 여행 (Large) / 골드 5

• DP 문제인데, 매번 왼쪽 아래 / 가운데 아래 / 오른쪽 아래로 이동할 수 있음
• 다만 두번 연속 동일한 방향으로 이동할 수는 없음
• DP[i][j][k]에 i행 j열에 도착했을 때 누적 연료의 최솟값 저장
  • 단 k==0일 땐 왼쪽 아래 방향으로, k==1일 땐 가운데 아래 방향으로, k==2일 땐 오른쪽 아래 방향으로 내려왔을 때를 계산
  • 이전 행에서 같은 방향으로 이동한 경우는 제외하고 점화식을 구성
• 시간 복잡도: $N$행 $M$열일 때, DP 테이블의 크기는 $N \times M \times 3$이므로 $O(N\times M)$
  • $N, M \leq 1000$이므로, 최대 $1,000,000$번 연산 -> 충분.

import sys
input = sys.stdin.readline

# N행, M열
N, M = map(int, input().split())
grid = []
for _ in range(N):
    grid.append(list(map(int, input().split())))
    
# DP[i][j][k]: i행 j열에 방문했을 때 누적 연료의 최솟값
# 단 k==0일 땐 왼쪽 아래, k==1일 땐 가운데 아래, k==2일 땐 오른쪽 아래로 이동한 것
DP = [[[float('inf')] * 3 for _ in range(M)] for _ in range(N)]

# 0행을 채우기
for j in range(M):
    for k in range(3):
        DP[0][j][k] = grid[0][j]
        
# 1행부터 채우기
for i in range(1, N):
    for j in range(M):
        # 왼쪽 아래로 내려온 경우
        if j != M - 1:
            DP[i][j][0] = min(DP[i - 1][j + 1][1], DP[i - 1][j + 1][2]) + grid[i][j]
        
        # 가운데 아래로 내려온 경우
        DP[i][j][1] = min(DP[i - 1][j][0], DP[i - 1][j][2]) + grid[i][j]
        
        # 오른쪽 아래로 내려온 경우
        if j != 0:
            DP[i][j][2] = min(DP[i - 1][j - 1][0], DP[i - 1][j - 1][1]) + grid[i][j]

# 정답 구하기
answer = min(min(DP[N - 1][j][k] for k in range(3)) for j in range(M))
print(answer)

1743. 음식물 피하기

백준 / 1743. 음식물 피하기 / 실버 1

• 상하좌우의 인접한 음식물은 덩어리를 형성
• BFS를 이용해 음식물이 있는 인접 칸을 모두 방문하면, 각 덩어리의 크기를 구할 수 있음
• BFS에서 방문 처리는 큐에 삽입할 때 한다는 점 잊지 말 것
  • 특히 맨 처음 노드의 방문 처리를 잊지 말 것
• DFS를 써도 인접 칸 방문이 가능하니 뭘 써도 됨 (하지만 난 재귀보단 큐가 좋아서 BFS 씀)
• 시간 복잡도: $N$행 $M$열일 때, BFS를 통해 최대 $N\times M$개 칸을 탐색 -> $O(N \times M)$
  • $N \leq 100, M \leq 100$이므로 최대 $10,000$번 연산 -> 충분.

from collections import deque
import sys

input = sys.stdin.readline

# BFS를 수행해서, 인접한 음식물 칸을 모두 방문하고 크기를 셈
def bfs(x, y):
    queue = deque([(x, y)])
    visited[x][y] = True    # 아차차 이걸 까먹을 뻔.
    count = 0
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    
    while queue:
        cx, cy = queue.popleft()
        count += 1
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = True
    
    return count

# 세로길이, 가로길이, 음식물 칸 수
N, M, K = map(int, input().split())
answer = 0

# 각 칸의 방문 여부
# 음식물이 없는 칸은 True.
# 음식물이 있는 칸은 방문 전 False, 방문 후 True.
visited = [[True] * (M) for _ in range(N)]

# 음식물이 떨어진 위치
marks = []
for _ in range(K):
    x, y = map(int, input().split())
    marks.append((x - 1, y - 1))
    visited[x - 1][y - 1] = False

# 음식물 떨어진 위치 - 미방문시 BFS로 방문 처리\
for x, y in marks:
    if not visited[x][y]:
        count = bfs(x, y)
        answer = max(answer, count)

print(answer)

14719. 빗물

백준 / 14719. 빗물 / 골드 5

• 처음엔 DFS/BFS 문제인 줄 알았는데, 놀랍게도 아니였음
• 각 층(높이)마다 블록이 설치된 위치 저장
• 각 층마다 블록 간 간격을 계산하면, 물이 고인 칸 수를 확인할 수 있음
• 시간 복잡도: 세로길이 $H$, 가로길이 $W$일 때, 모든 가로 위치에 블록이 최대 높이로 쌓인 경우 $O(H \times W)$
  • $H \leq 500, W \leq 500$이므로 최대 $25,000$번 연산 -> 충분.

H, W = map(int, input().split())
heights = list(map(int, input().split()))

# 높이별 블록의 존재 위치 저장
# blocks[i]: i층에서 블록의 위치

blocks = [[] for _ in range(H + 1)]
for j in range(len(heights)):
    for i in range(1, heights[j] + 1):
        blocks[i].append(j)

# 고이는 빗물의 총량 계산
# 블록 간 간격을 계산하면 됩니다
answer = 0
for i in range(1, H + 1):
    for j in range(1, len(blocks[i])):
        answer += (blocks[i][j] - blocks[i][j - 1] - 1)
    
print(answer)