구름톤 챌린지 Day 11 - Day 12[탐색과 DP]

[문제 11]

N = int(input())
A, B = map(int, input().split())

dp = [9999999 for _ in range(N + 1)]

dp[0] = 0
for i in range(N + 1):
    if i - A >= 0:
        dp[i] = min(dp[i], dp[i-A] + 1)
    if i - B >= 0:
        dp[i] = min(dp[i], dp[i-B] + 1)

if dp[-1] == 9999999:
    print(-1)
else:
    print(dp[-1])

동적프로그래밍 문제는 제대로 풀어본 적이 없어서 이 문제 또한 매우 간단해보이지만 어렵게 느껴졌다. 
먼저 dp 배열은 통증 수치가 i 일 때, 통증 수치를 0으로 만들기 위해 필요한 아이템의 최소 개수라 설정한다. 
< dp 배열 초기화 >
min 값을 찾아나가야하기 때문에 초기 배열은 매우 큰 값으로 설정해주어야한다. 
-> 따라서 무한대를 의미하기 위해서 float('inf')로 초기화할 수 있다. 
i 값에 따라서 통증 수치가 i - A일 때 사용한 아이템 개수에  + 1을 하면 A 아이템을 하나 더 사용한다는 의미다. 
그 외의 부분에서는 inf 값과 inf + 1 값을 비교하는 것으로 inf 로 채워진다. 
B도 동일하게 진행하면 위와 같은 결과를 출력할 수 있다. 

[문제 12]

from collections import deque
n = int(input())
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))
    
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]

result = 0

# dfs 
def dfs(x,y):
    stack = [[x, y]] 
    while stack:
        x, y = stack.pop()
        if not graph[x][y]:
            continue
        graph[x][y] = 0 
        for dx, dy in moves: 
            nx, ny = x + dx, y + dy 
            if 0 <= nx < n and 0 <= ny < n: 
                if graph[nx][ny]:
                    stack.append([nx, ny])
# bfs
def bfs(x, y):
    q = deque([[x,y]])
    while q:
        x, y = q.popleft()
        if not graph[x][y]:
            continue
        graph[x][y] = 0
        for dx, dy in moves:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n:
                if graph[nx][ny]:
                    q.append([nx, ny])
for i in range(n):
    for j in range(n):
        if graph[i][j]: 
            #dfs(i, j)
            bfs(i, j)
            result += 1
print(result)

먼저, 이 문제가 DFS/BFS를 사용하는 문제라는 것을 알아차려야한다. 
문제에서 원하는 것은 인접한 집들의 그룹의 개수이다. 해당 그룹의 개수를 구현하기 위해서는 탐색 알고리즘인 DFS/BFS가 필요하다. 또한 기존의 DFS/BFS 문제와 다르게 상하좌우만을 탐색하면서 그룹의 개수를 찾아야한다. 
따라서 탐색 방향 배열을 먼저 만들어주고 진행하였다. 
DFS는 stack을, BFS는 deque를 활용하며 비재귀 DFS와 BFS의 알고리즘은 거의 유사하다. 
총 4방향을 돌면서 상하좌우의 인접한 값을 확인하며 그룹을 구하면 마무리되는 문제다. 
그래프 방문 여부는 현재 0과 1로 그래프가 구성되어있고 1의 그룹을 찾고 싶기 때문에 방문한 1에 대해서 0으로 값을 변경하는 식으로 그래프 방문 여부를 나타낼 수 있다.