정리하며 삽시다

"배열에 존재하는 모든 연결 요소의 크기를 계산한다"라고 하는 2번 조건은 함정에 가깝다.

"처음에는 크기가 K 이상인 연결 요소가 존재하지 않는다"와 "문자를 적을 칸은 비어있음이 보장된다."

이 두 조건에 따르면, 입력이 주어졌을 때만 그 부분에 대해서 DFS나 BFS를 수행하면 된다.

from collections import deque
import sys
input = sys.stdin.readline


def BFS(x, y, value, graph):
    queue = deque([(x, y)])
    
    footprint = [(x, y)]
    visited = [[0] * length for _ in range(length)]
    visited[x][y] = 1
    
    while queue:
        x, y = queue.popleft()
        
        for dx, dy in dxy:
            nx = x + dx
            ny = y + dy
            
            if 0 <= nx < length and 0 <= ny < length\
            and visited[nx][ny] == 0 and graph[nx][ny] == value:
                visited[nx][ny] = 1
                queue.append((nx, ny))
                footprint.append((nx, ny))
                
    if len(footprint) >= K:        
        for cx, cy in footprint:
            graph[cx][cy] = "."
        
    return


length, K, question = map(int, input().split())
graph = [list(input().rstrip()) for _ in range(length)]

# UP, DN, LFT, RGT
dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for _ in range(question):
    changeX, changeY, alphabet = map(str, input().split())
    graph[int(changeX)-1][int(changeY)-1] = alphabet
    BFS(int(changeX)-1, int(changeY)-1, alphabet, graph)
    
for line in graph:
    print(''.join(line))

다른 BFS와 코드가 유사하여 특별하게 설명할 부분은 없다.

다만 dx, dy로 선언한 방향 list는 dxy로 index가 아니라 값으로 직접 계산할 수 있게 수정했다.

아무래도 index로 접근하는 것보다는 값을 직접 순회하는 것이 빠르기 때문이다.

for _ in range(question):
    changeX, changeY, alphabet = map(str, input().split())
    changeX = int(chagneX) - 1
    changeY = int(changeY) - 1
    
    graph[changeX][intchangeY] = alphabet
    BFS(intchangeX, changeY, alphabet, graph)

[x][y]에는 이미 온점(.)이 있을 테니, alphabet으로 바꿔준다.

그리고 해당 위치에서부터 BFS를 수행한다.

def BFS(x, y, value, graph):
    ''' 초기화 코드 작성 '''
    
    footprint = [(x, y)]
    
    ''' BFS 코드 작성 '''
                
    if len(footprint) >= K:        
        for cx, cy in footprint:
            graph[cx][cy] = "."
        
    return

footprint 객체는 BFS로 탐색한 위치를 저장하는 list다.

만약 footprint의 개수가 K보다 크거나 같으면 footprint에 해당하는 모든 좌표를 '."으로 바꾼다.

조금은 재미있는 문제다.

일반적인 BFS와 같되, 각 도시들을 하나씩 망가뜨려 갈 수 없는 상태로 만든다.

이런 모든 경우를 돌아보면서, 어떤 도시를 갈 수 없을 때, 최단 거리는 얼마인지 묻는 문제이다.

from collections import deque
from copy import deepcopy as dcopy
import sys
input = sys.stdin.readline


# do BFS
def BFS(start, end, graph):
    queue = deque([start])
    
    visited = [0] * (city + 1)
    visited[start] = 1
    
    while queue:
        now = queue.popleft()
        
        if now == end:
            return visited[end]

        for next in graph[now]:
            if visited[next] == 0:
                queue.append(next)
                visited[next] = visited[now] + 1
                
    return -1
    

city, road, start, end = map(int, input().split())
GRAPH = [[] for _ in range(city+1)]

# Adjacency List element add for bidirected
for _ in range(road):
    a, b = map(int, input().split())
    GRAPH[a].append(b)
    GRAPH[b].append(a)
    
# Adjacency List each element sort
for line in GRAPH:
    line.sort()

# Calculating shortest path that contain to pass cities
for i in range(1, city+1):
    if i == start or i == end:
        print(-1); continue
        
    graph = dcopy(GRAPH)    
    graph[i].clear()
    
    answer = BFS(start, end, graph)
    print(answer)

이번 문제도 사실상 다른 그래프 문제와 크게 다를 바가 없다.

하지만, 이동 경로를 판단하여 순차적으로 도시를 들려야 하기에 DFS보다는 BFS가 맞다.

from copy import deepcopy as dcopy

입력 코드, 인접 리스트로 선언하고 정렬하는 코드는 전부 생략한다.

기존에 풀었던 방법과 동일하여 굳이 설명할 필요가 없기 때문이다.

이 문제를 풀 때 핵심은 i번째는 건너뛰어야 한다.

for i in range(1, city+1)로 i를 받고, node == i라면 무시하는 방법을 사용해도 된다.

하지만 시간과 메모리 제한을 명시하지 않는 구름 사이트 특성상, 메모리 한계가 궁금해졌다.

그래서 굳이 copy 라이브러리를 사용하여 구현했다.

그럼에도 무난히 통과한 것을 보니 MLE보다는 TLE에 민감한 듯하다.

# Calculating shortest path that contain to pass cities
for i in range(1, city+1):
    if i == start or i == end:
        print(-1); continue
        
    graph = dcopy(GRAPH)    
    graph[i].clear()
    
    answer = BFS(start, end, graph)
    print(answer)

반복문을 돌면서 graph에 처음에 초기화한 GRAPH를 deepcopy한다.

그리고 i번째는 아예 지워버린다(clear()). 지운 graph를 기준으로 BFS를 돌면서 최단 거리를 찾는다.

# do BFS
def BFS(start, end, graph):
    while queue:
        now = queue.popleft()
        
        if now == end:
            return visited[end]
                
    return -1

일반적인 BFS와 다른 점은 위의 코드뿐이다.

BFS를 돌면서 now가 end 지점과 같다면, end의 visited 값을 반환한다.

이때 visited는 단순히 방문 여부만 있는 0과 1이 아니라, 몇 번째로 갔는지를 의미하는 int가 들어간다.

모든 부분을 탐색했음에도 if now == end로 함수를 빠져나가지 못하는 경우가 있다.

이 경우는 그래프에 end 지점이 없다는 말과 같다.

그런 경우 -1을 반환하여 갈 수 없음을 알려주어야 한다. 

이번에도 여김없이 나온 '틀린 카테고리 문제'다. 무슨 소리냐고? 그래프에서 DP 문제를 냈다는 이야기이다.

3주차 그래프 문제를 4주차에 내고, 4주차 이 문제를 3주차에 내면 되는 거 아닌가... 자꾸 생각이 든다.

문제를 처음 보고 나서 "이게 DP인가?"라는 생각을 했다.

그냥 가로 세로 선 개수를 센 다음에 곱해서 더하면 끝 아닌가...? 브루트 포스 아닌가?

그래서 생각나는 대로 우선 코드를 짰다.

import sys
input = sys.stdin.readline


def DrawLine(x, y, dir):
    global square
    x -= 1
    y -= 1
    
    if dir == "U" or dir == "D":
        nx = dx[dr.index(dir)]
        
        while (0 <= x and x < length):
            square[x][y][0] += 1
            x += nx
        
    else:
        ny = dy[dr.index(dir)]
        
        while (0 <= y and y < length):
            square[x][y][1] += 1
            y += ny


length, half_line = map(int, input().split())
square = [[[0, 0] for _ in range(length)] for _ in range(length)]  # horizontal, vertical

# UP, DN, LFT, RGT
dr = ["U", "D", "L", "R"]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(half_line):
    startX, startY, dir = map(str, input().split())
    
    DrawLine(int(startX), int(startY), dir)
    
answer = 0
for x in range(length):
    for y in range(length):
        answer += square[x][y][0] * square[x][y][1]
        
print(answer)

ㅇㅇ

# UP, DN, LFT, RGT
dr = ["U", "D", "L", "R"]
dxy = [-1, 1, -1, 1]

dxy를 선언해주었다. 방향에 따른 값을 이용하기 위해 dr을 선언해주었다.

U, D, L, R 중 하나의 방향을 dr에서 index로 찾는다. 그리고 index에 맞춰 dxy를 변경한다.

이때 dx, dy로 선언하지 않고, dxy의 0이 없는 list를 선언한 이유는 간단하다.

가로 선과 세로 선은, 다른 한 축이 움직이지 않기 때문이다.

가로가 움직일 때는 세로가 가만히 있고, 세로가 움직일 때는 가로가 가만히 있는다.

이동을 할 때 둘 중 하나만 이동해주면 되기 때문에 한 번에 선언해도 상관이 없다.

if dir == "U" or dir == "D":
    nx = dxy[dr.index(dir)]

    while (0 <= x and x < length):
        square[x][y][0] += 1
        x += nx

else:
    ny = dxy[dr.index(dir)]

    while (0 <= y and y < length):
        square[x][y][1] += 1
        y += ny

sqaure는 사각형의 3차원 list이다. 2차원으로 가장 먼저 크기에 맞춰 선언한다.

그 다음 각 요소를 가로 선과 세로 선을 각각 저장한 하나의 list로 선언한다. 결과적으로 3차원이 된다.

세로 선을 0번째 index 값으로, 가로 선을 1번째 index 값으로 취급한다.

현재 위치부터 시작하여 범위 내에 있다면  while문으로 해당 직선에 1을 더해준다.

U와 D의 경우 x값만 바뀌는 것이기에 x += nx 연산만 해주면 된다.

L과 R의 경우 y값만 바뀌는 것이기에 y += ny 연산만 해주면 된다.

answer = 0
for x in range(length):
    for y in range(length):
        answer += square[x][y][0] * square[x][y][1]
        
print(answer)

DrawLine() 함수 연산 이후, 각 sqaure 칸은 가로 세로 선의 개수가 있다.

그럼 모든 경우에 두 값을 곱한 뒤, 더해주면 정답이다.

하지만 의문이 들었다.

선을 어떻게 그리는지 정보가 주어지고, 그대로 따라가 선을 그려준다. (값을 업데이트한다.)

그런 다음 모든 칸에 대해서 돌면 DP가 아니라 Brute force가 아닌가?

하여 정해 코드에 대해 이것이 왜 DP인지 질문해보았다.

구름은 어떤 측면에서 DP라고 생각하는 걸까?

질문에도 썼지만, DP의 핵심은 caching이다.

그것이 memoization이든 tabulation이든 어쨋든 같은 연산을 방지하기 위한 저장이다.

구름은 모든 선을 그려 미리 값을 저장하는 것 자체를 caching으로 본 거다.

구름 입장에서 Brute force가 되려면 모든 경우를 하나하나 탐색해야 한다고 한다.

선 정보를 모두 저장한 다음, 이중 반복문으로 모든 칸을 순회한다.

순회하면서 그때그때 선 정보를 확인하여 중첩 점이 몇 개인지 확인한다.

그럼 특정 반직선에 대해 여러 번 계산하는 경우가 생길 것이다. 이것이 Brute force라는 거다.

이런 같은 연산을 방지하고, 값을 저장하여 해답에 접근했으니 DP라는 것이다.

이 부분에 대해서 약 1시간가량 친구와 토론을 했다.

DP란 결국 무엇인가,  저것은 단순한 추상화(의사 코드; 개념을 그대로 코드로 옮긴 것)는 아닌가,

접점의 개수를 구하기 위해 저장한다는 것을 어떤 측면에서 바라보아야 하는가,

특정 상황에서 문제를 해결하기 위한 알고리즘을 이분법으로 분류할 수 있는가,

과거의 상태를 불러왔다고 말할 수 있는가, 내가 옳다고 생각한 것이 정말로 옳은가,

알고리즘의 시시비비를 확인하기 전 이 문제에서 본질(핵심)은 과연 무엇인가.

장황하지만, 요약하자면 '코에 걸면 코걸이 귀에 걸면 귀걸이'다.

'문제'라는 것은 '정답을 구하기 위해 책에 있는 잘 정리된 정보' 만 있는 게 아니다.

일상생활에서 다툼일 수도 있고, 누구도 해결하지 못한 어려움일 수도 있다.

또한, 다양한 이해관계가 얽힌 상황일 수도 있으며, 생각보다 간단한 기본일 수도 있다.

즉, 용어에 함몰되어 이게 맞는지?를 아는 것보다 이 상황의 문제는 뭐지?를 아는 것이 중요하다.

우리에게 주어지는 '문제'는 알고리즘 분류만으로 표기할 수 없는 경우가 태반이다.

본인이 옳다고 믿는 것을 옳지 않다고 생각할 의지가 필요하다.

다양한 문제를 해결하고 발전하기 위해서는, 각양각색의 의견을 경청해야 한다.

사실 일반적인 DFS와 BFS와 전혀 다를 게 없는 문제다.

그저 간선의 수를 셀 줄 아는가? 정렬하는 방법을 알고 있는가?를 확인하는 문제다.

그리고 16일차 문제를 여전히 BFS로 푸는 것을 보고, 굳이 다른 방법으로 풀 필요가 없다고 생각했다.

따라서 본 문제도 BFS로 문제를 해결했으며, 기존 BFS와 다른 점만을 작성한다.

from collections import deque
import sys
input = sys.stdin.readline

def BFS(start: int, answer: list):
    queue = deque([start])
    visited[start] = 1
    components = [start]
    
    while queue:
        now = queue.popleft()
        
        for next in graph[now]:
            if visited[next] == 0:
                queue.append(next)
                visited[next] = 1
                components.append(next)
        
    components.sort()
    
    line = 0
    for v in components:
        line += len(graph[v])
    line //= 2
    
    components.append(len(components))
    components.append(line / components[-1])
    answer.append(components)
    
    return


computer, vertex = map(int, input().split())
graph = [[] for _ in range(computer+1)]
answer = [] # ["components", "len", "density"]
visited = [0] * (computer+1)

for _ in range(vertex):
    A, B = map(int, input().split())
    graph[A].append(B)
    graph[B].append(A)

for i in range(1, computer+1):
    if not visited[i]:
        BFS(i, answer)
    
answer.sort(key = lambda x: (-x[-1], x[-2], x[0]))
    
for Inode in range(answer[0][-2]):
    print(answer[0][Inode], end=" ")

전체 코드에서 간선의 개수를 세는 코드만 조금 다르게 추가해주었다.

굳이 이중 반복문으로 노드를 탐색하고, 조건문으로 소속 여부를 판별할 필요가 없다.

정해 코드에서도 이 방법을 사용했는데, '양방향 연결'이라는 특징을 알면 간단하게 구할 수 있다.

answer = [] # ["components", "len", "density"]

우선 본 코드에서 핵심으로 사용할 객체 answer다.

해당 list에는 3개의 요소가 들어간다. components, len, density.

components는 하나로 연결된 모든 노드 번호들이 들어간다.

len은 components의 개수, density는 components의 밀도를 말한다. 

def BFS(start: int, answer: list):
    components = [start]
    
    ''' BFS로 연결 노드를 전부 찾는 코드 작성 '''
        
    components.sort()
    
    line = 0
    for v in components:
        line += len(graph[v])
    line //= 2
    
    components.append(len(components))
    components.append(line / components[-1])
    answer.append(components)
    
    return

BFS로 같은 통신망(그래프)에 속한 노드를 찾는 코드 설명은 생략한다.

생략한 코드를 실행하고 나면, components에는 연결된 모든 노드가 오름차순으로 들어가있다(sort()).

처음에도 간단하게 말했지만, 이 문제는 양방향 연결 상태이다.

1에서 3으로 가는 연결이 있다면, 3에서 1로 가는 연결도 있다. 그리고 이 두 연결은 같은 연결로 취급한다.

코드에서 모든 components를 구해서 저장했다.

그럼 반복문으로 components에 있는 노드들에서, 연결된 노드의 개수를 모두 구한다.

연결된 노드 개수는 graph로 처음에 입력받고 인접 리스트로 정리한, '길이'와 같다.

모든 연결을 다 더한 뒤에 2로 나누면 끝이다.

마지막으로 components에 길이(len(components))와 밀도(line / components[-1])를 추가하면 끝이다.

''' 입력받는 코드 작성 '''

''' BFS로 모든 요소 확인하는 코드 작성 '''
    
answer.sort(key = lambda x: (-x[-1], x[-2], x[0]))
    
for Inode in range(answer[0][-2]):
    print(answer[0][Inode], end=" ")

문제의 조건은 순서대로 3개이다.

밀도가 가장 높을 것, 집합의 길이가 가장 짧을 것, 노드의 번호가 가장 작을 것.

즉 밀도의 내림차순, 집합 길이의 오름차순, 노드 번호의 오름차순 정렬을 필요로 한다.

BFS() 코드에서 집합 길이는 뒤에서 2번째에, 밀도는 뒤에서 1번째에 저장했다.

sort() 함수의 key로 (-x[-1], x[-2], x[0])로 정렬할 수 있다는 이야기이다.

정렬을 하고 나면 가장 처음의 list가 정답이다.

모든 요소를 unpacking(*)으로 풀면 안 된다. 길이와 밀도 값도 포함하기 때문이다.

하지만, 첫 번째 노드의 개수를 알고 있다. [-2]에 말이다.

즉, answer[0][-2]만큼 반복문으로 돌면서, answer[0][Inode]를 출력하면 정답이다.

백준 바이러스와 유사한 문제이다. 그래프로 연결할 때, 몇 개의 집합이 있는가 묻는 문제이다.

DFS와 BFS 방식 두 가지으로 모두 해결했지만, 여기에는 조금 다른 방법을 적어본다.

3주차에서 '탐색'이라는 카테고리에서 DFS와 BFS 응용을 했으니, 4주차에서는 진짜 '그래프'로 풀어보고자 했다.

구름의 출제 의도가 그것이 아닐까? 라는 생각이 들어 다른 그래프 알고리즘을 적용해보았다.

그게 아니라면 DFS와 BFS를 굳이 2주에 걸쳐 할 필요가 없으니 말이다.

# ---------- Import ----------
import sys
input = sys.stdin.readline

# ---------- Function ----------
def Union(start, end, parent):
    start_root = Find(start, parent)
    end_root = Find(end, parent)
    
    # Setup parent node, which is more smaller
    if start_root < end_root:
        parent[end_root] = start_root
    else:
        parent[start_root] = end_root


def Find(current, parent):
    # Current node is root
    if parent[current] == current: return current
    # Find root node
    else: return Find(parent[current], parent)


def Solution(N, graph):
    # Init state, each node's parent node is itself
    parent = [v for v in range(N+1)]
    
    for s in range(1, N+1):
        for e in graph[s]:
            
            # Bidirected island
            if s in graph[e]:
                Union(s, e, parent)
                
    answer = set()
    for v in range(1, island+1):
        answer.add(Find(v, parent))
                
    return len(answer)

# ---------- Main ----------
island, bridge = map(int, input().split())

graph = {v:[] for v in range(island+1)}
for _ in range(bridge):
    key, value = map(int, input().split())
    graph[key].append(value)
    
answer = Solution(island, graph)
print(answer)

Union-Find, 다른 말로는 DSU(Disjoint Set Union)으로 부르는 알고리즘이다.

각 노드(node)를 돌면서, 연결된 노드들 사이에서 root를 찾아 저장한다.

모든 노드를 돌면 각 노드의 저장값은, 루트 노드만이 존재하게 된다.

중복을 제거하면 루트 노드들의 값이 1개씩만 존재할 것이고, 이는 곧 집합의 수와 같다.

밑에서 설명할 알고리즘에서는 Union-Find라는 용어를 기준으로 진행한다.

# ---------- Function ----------
def Find(current, parent):
    # Current node is root
    if parent[current] == current: return current
    # Find root node
    else: return Find(parent[current], parent)

Union-Find에서 Find를 담당하는 알고리즘이다.

탐색이라는 뜻의 Find로, 특정 노드가 어떤 루트 노드에 속한 그래프인지 탐색하는 알고리즘이다.

parent는 특정 index에 index의 루트 노드를 저장한 list다.

저장한 값과 index가 같다면, 노드 자신이 루트 노드다. 즉, 현재 값(current)를 반환하면 된다.

하지만 저장한 값과 index가 다르다면, 저장한 값을 따라서 루트 노드를 찾아간다.

# ---------- Function ----------
def Union(start, end, parent):
    start_root = Find(start, parent)
    end_root = Find(end, parent)
    
    # Setup parent node, which is more smaller
    if start_root < end_root:
        parent[end_root] = start_root
    else:
        parent[start_root] = end_root

Union-Find에서 Union을 담당하는 알고리즘이다.

조합이라는 뜻의 Union로, 각 노드들을 특정 루트 노드에 속하게 그래프를 합치는 알고리즘이다.

두 개의 start, end 노드를 입력받고, 두 노드를 루트 노드를 기준으로 하나의 그래프로 합친다.

밑의 함수에서 살펴보겠지만, Union() 함수에 들어온 두 노드는 전제가 '같은 그래프에 속하는 노드'다.

start 노드의 루트 노드는 start_root로, end 노드의 루트 노드는 end_root로 Find() 함수로 계산한다.

여기서는 루트 노드를 더 작은 노드를 기준으로 삼았다.

큰 노드를 기준으로 삼아도 상관없다. 어차피 '집합의 개수'를 세는 문제다. 문제에 따라 조건을 달리 하자. 

두 개가 같은 그래프이고, 각각의 루트 노드를 가져왔다. 그럼 더 작은 노드를 기준으로 루트 노드를 변경해준다.

# ---------- Function ----------
def Solution(N, graph):
    # Init state, each node's parent node is itself
    parent = [v for v in range(N+1)]
    
    for s in range(1, N+1):
        for e in graph[s]:
            
            # Bidirected island
            if s in graph[e]:
                Union(s, e, parent)
          
    answer = set()
    for v in range(1, island+1):
        answer.add(Find(v, parent))
                
    return len(answer)

Union() 함수와 Find() 함수를 같이 묶어서 사용하는 Solution() 함수이다.

모든 노드는 초기화(parent)한다. 초기 상태는 자기 자신이 루트 노드인 상태이다.

인접 리스트를 활용하여, 모든 노드를 하나하나 탐색한다.

start 노드(s)와 end 노드(e)가 서로 양방향으로 연결되어 있다면 Union으로 연결한다.

모든 노드를 탐색하고 나면, parent에는 각 index의 루트 노드가 저장된 상태일 것이다.

정답을 넣을 set() 자료 구조로, answer 객체를 선언한다.

마지막으로 모든 노드의 루트값을 Find() 함수로 찾아 저장한다.

문제의 정답은 '집합의 개수'이니 answer의 길이(len)를 반환하면 끝이다.

# Correct case
for v in range(1, island+1):
    answer.add(Find(v, parent))
        
# Wrong case
list(set(parent))

# Counter example
# 5 8
# 1 5
# 5 1
# 2 3
# 3 2
# 3 4
# 4 3
# 4 5
# 5 4

이때 조심할 점은 parent를 활용한 정답 추출이다.

parent에는 각 노드에 해당하는 루트 노드가 저장된 것은 틀림없다.

그렇다면 굳이 Find()로 다시 찾을 필요 없이, parent를 set()으로 감싼 길이를 반환하면 되지 않은가?

않다. 해당 Union-Find 알고리즘에서는 순서라는 큰 제약이 있다.

반례(counter example)를 살펴보자.

1 2 3 4 5가 있는 상태로, 1-5, 2-3, 3-4, 4-5가 양방향으로 연결되어 있는 상태다.

인접리스트를 초기화하고, 노드를 index 순서대로 돌면서 루트 노드를 검색하고 변경한다.

그럼 parent는 [1, 1, 1, 1, 1]이 되어야 할 것 같지만, 접근 순서 때문에 [1, 1, 2, 2, 1]이 된다.

1과 2는 가장 끝과 끝이지만 분명 연결된 하나의 그래프이다.

순서 때문에 발생하는 오류이니 이 점을 유의하자. 

구름톤 챌린지 3주, 15일차 문제 과일 구매이다.

문제를 어느정도 접해본 사람이라면, 위 문제를 보고 한 가지가 떠올라야 한다. '분할 가능한 배낭 문제'

가방 최대 한도가 소지한 돈(K)에 해당하고, 각 물건의 무게들은 포만감(C)에 해당한다.

fruits, MONEY = map(int, input().split())

fruit_list = []
for _ in range(fruits):
    fruit_price, fruit_full = list(map(int, input().split()))
    piece_full = fruit_full // fruit_price
    fruit_list.append([piece_full, fruit_price, fruit_full])

fruit_list.sort(key=lambda x: -x[0])

answer = 0
for piece_full,fruit_price, fruit_full in fruit_list:
    if MONEY >= fruit_price:
        answer += fruit_full
        MONEY -= fruit_price
        
    else:
        answer += MONEY * piece_full
        break
    
print(answer)

위에서 언급했던 것처럼 가방 한도가 가격으로, 물건 무게가 포만감으로 바뀌었을 뿐 문제 자체는 같다.

잘 알려진 분할 가능한 가방 문제이니 만큼, 모르더라도 쉽게 풀 수 있다.

동적 계획법 카테고리였다면, '0-1 가방 문제(0-1 knapsack problem)'가 나왔어야 했다. 

fruit_list = []
for _ in range(fruits):
    fruit_price, fruit_full = list(map(int, input().split()))
    piece_full = fruit_full // fruit_price
    fruit_list.append([piece_full, fruit_price, fruit_full])

비교를 위한 조각당 포만감(piece_full)을 추가로 계산하여 list에 넣어준다.

이때 가격은 1로 고정이고, 조각당 포만감(piece_full)과 총 가격(fruit_price)을 알고 있다.

따라서 연산으로 총 포만감(fruit_full)을 구할 수 있어 추가하지 않아도 상관없다.

하지만, 굳이 따로 또 연산을 하는 것보다 이미 주어진 값을 활용하는 것이 효율적이라 같이 저장한다.

fruit_list.sort(key=lambda x: -x[0])

최대의 포만감을 찾기 위한, 이 문제는 그리디 알고리즘이다.

가장 높은 포만감을 주는 과일을 우선적으로 찾아서 구매하면 된다.

이때 모든 조각 가격은 1로 같기 때문에, 조각당 포만감을 기준으로 내림차순 정렬을 한다.

for piece_full,fruit_price, fruit_full in fruit_list:

fruit_list를 돌면서 각 요소를 unpacking하여 직접 받아온다.

for _ in range(something)이나 fruit_list[0], fruit_list[1], fruit_list[2]처럼 index로 접근하면 더 오래 걸린다.

if MONEY >= fruit_price:
    answer += fruit_full
    MONEY -= fruit_price
        
else:
    answer += MONEY * piece_full
    break

문제를 모르고 있다하더라도, 논리로 이해하면 작성할 수 있는 코드 부분이다.

이미 조각당 포만감 순서대로 내림차순 정렬이 되어있는 상태이다.

즉, 순서대로 이미 최선의 선택을 할 수 있다는 말과 같다.

이때 이 과일을 통째로 살 수 있다면?(MONEY >= fruit_price)

다 사면 된다(MONEY -= fruit_price). 굳이 조각으로 하나하나 계산할 필요가 없다.

그렇게 내가 가진 돈으로 과일을 통째로 사다가, 돈이 부족해지는 경우가 온다(else).

그럼 남은 돈으로 현재 과일 조각을 전부 사면 된다(answer += MONEY * piece_full).

다음 과일은 고려하지 않아도 된다.

어차피 수중에 있는 돈으로는 다음 과일은커녕 지금 과일도 다 못 사는 상황이고,

설령 다음 과일을 살 수 있다고 하더라도, 지금 과일의 조각당 포만감이 높다는 사실을 알고 있다.

구름톤 챌린지 3주, 14일차 문제 작은 노드이다.

그래프를 구현할 줄 알고, 약간의 논리적 사고가 가능하다면 풀 수 있는 문제이다.

코드에 들어가기 전에 문제 해석을 해보자.

'한 번 방문한 노드는 다시 방문할 수 없으며, 번호가 가장 작은 노드로 이동'한다.

이는 DFS와 BFS 중 DFS로 문제를 구현하라는 뜻이다.

# ---------- Import ----------
import sys
sys.setrecursionlimit(2002)

# ---------- Function ----------
def DFS(graph, v, visited):
    global last_node
    
    visited[v] = True
    last_node.append(v)

    for i in graph[v]:
        if not visited[i]:
            DFS(graph, i, visited)
            return

# ---------- Main ----------
node, edge, start = map(int, input().split())
graph = [[] for _ in range(node+1)]
visited = [False] * (node+1)

for _ in range(edge):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for i in range(node+1):
    graph[i].sort()

last_node = []
DFS(graph, start, visited)
print(sum(visited), last_node[-1])

주의할 점을 나열해보자.

1. BFS가 아니라 DFS 그래프 구현이다.

2. 그래프를 이루는 간선은 양방향 간선이다.

3. 이동할 수 있는 노드가 없을 때, 그대로 종료한다.

4. 노드의 개수는 최대 2000개로, 재귀에 조심하자.

5. si, ei 입력에 속지말자. 오름차순으로 들어온다는 보장이 없다. 

# ---------- Import ----------
import sys
sys.setrecursionlimit(2002)

DFS로 구현한다는 말은 재귀 함수를 사용한다는 말과 동일하다.

노드 최대 개수는 2000개로, 최악의 경우 인접 행렬로 구현한다면 2000 * 2000 = 4,000,000의 탐색을 할 수도 있다.

따라서 최소 4백만의 한도를 갖게끔 제한을 풀어줘야 한다.

인접 리스트의 경우, 노드 최대 개수는 2000이므로 2000으로 풀어주면, 안 된다.

sys.setrecursionlimit(N)의 정확한 의미는, Python의 stack 공간을 N만큼 설정하라는 의미이다.

이때 main 함수 자체도 stack 공간에 쌓이게 된다.

즉, main에서 하나, 호출할 때 하나씩 차지하게 되므로 2000번째 노드를 검사하기 위해서는 2002만큼 공간이 필요하다.

메모리 저장과 Heap, stack 공간에 대한 개념을 모른다면 따로 공부하자.

빠듯하게 선언을 해서 2002로 한 것이지, 여유롭게 3000, 5000, 1000000으로 해도 상관은 없다.

하지만 그만큼 공간을 차지하기에, 자신이 구현하려는 방법(인접 행렬, 인접 리스트)과 상황에 따라 맞게 선언하자. 

왼쪽은 인접 리스트 방식으로 노드와 간선 값이 있을 때, 탐색 순서대로 출력하는 기본 코드이다.

그리고 오른쪽의 코드는 구름톤 챌린지에서 사용하는 DFS 코드이다.

다른 점은? print() 대신 노드를 last_node에 추가했다는 것과 return의 유무 뿐이다.

마지막으로 검사를 한 지점에서 빠져나와야 하기에, 모든 공간을 다 탐색한 뒤에는 돌아갈 필요없이 return하면 된다.

# ---------- Main ----------
node, edge, start = map(int, input().split())
graph = [[] for _ in range(node+1)]
visited = [False] * (node+1)

DFS와 BFS를 구현하는 방법에는 인접 행렬과 인접 리스트 방법이 있다.

인접 행렬은 N * N 크기의 공간을 선언해서, 존재하는 간선만 1로 초기화하는 방법이다.

인접 리스트는 빈 2차원 공간을 선언해서, 인접한 노드 값으로 초기화하는 방법이다.

graph는 인접 리스트용으로 초기화했고, visited는 방문 여부를 확인하는 list이다.

# ---------- Main ----------
for _ in range(edge):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

양방향 간선이기 때문에 [a] = b도 넣고, [b] = a도 넣어줘야 한다.

# ---------- Main ----------
for i in range(node+1):
    graph[i].sort()

처음에 주의했듯이, 순서대로 들어오는 것이 아니다.

1 6, 1 4로 들어오고 이를 그대로 실행한다면 4보다 6을 먼저 탐색할 것이다.

따라서 각 항목에 대해서 정렬을 해줘야 한다.

이 방법이 싫다면 인접 행렬을 사용하면 된다.

# ---------- Main ----------
last_node = []
DFS(graph, start, visited)
print(sum(visited), last_node[-1])

visited는 0과 1로만 이루어진 list이다. visited를 다 더하면 방문한 노드 개수가 된다.

마지막으로 방문한 노드들을 추가할 last_node를 선언한다.

방문한 노드들을 순서대로 담고, 마지막에 return으로 빠져나오면 마지막 요소([-1])가 마지막 탐색 노드이다.

구름톤 챌린지 3주, 13일차 문제 발전기 (2)이다.

발전기 다음 바로 발전기 2가 나왔으니, 그 전과 매우 유사한 알고리즘으로 문제를 해결할 수 있다.

# ---------- Import ----------
from collections import deque
import sys
input = sys.stdin.readline

# ---------- Function ----------
def BFS(x, y, value):
    global visited, apartment
    
    count = 1
    
    queue = deque([(x, y)])
    visited[x][y] = 1
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < length and 0 <= ny < length\
                and visited[nx][ny] == 0 and graph[nx][ny] == value:
                    count += 1
                    queue.append((nx, ny))
                    visited[nx][ny] = 1
        
    return count

# ---------- Main ----------
length, K = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(length)]

visited = [[0] * length for _ in range(length)]
apartment = [[i, 0] for i in range(31)]

# UP, LFT, RGT, DN
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

for r in range(length):
    for c in range(length):
        if BFS(r, c, graph[r][c]) >= K:
            apartment[graph[r][c]][1] += 1

apartment = sorted(apartment, key=lambda x: (-x[1], -x[0]))      
print(apartment[0][0])

발전기 문제와 마찬가지로 BFS를 통해 구현했다.

# ---------- Import ----------
from collections import deque
import sys
input = sys.stdin.readline

BFS를 위한 collections 라이브러리의 deque 모듈을 호출했다.

마을 크기가 최대 1000, 집의 상태가 최대 30으로, 입력이 많다고 생각해 빠른 입력을 위해 sys를 사용했다.

# ---------- Function ----------
def BFS(x, y, value):
    global visited, apartment
    
    count = 1

BFS를 돌면서, 전역 변수(global)인 visited와 apartment에 대한 수정이 필요하다.

따라서 visited와 apartment를 global로 받아왔다.

또한 집이 K개 이상 있어야 하나의 단지로 인정해주기 때문에, 개수를 세는 count를 선언했다.

이때 BFS를 들어오면 무조건 1개는 있는 상태이기에, 1로 초기화했다.

# ---------- Function ----------
if 0 <= nx < length and 0 <= ny < length and visited[nx][ny] == 0 and graph[nx][ny] == value:
    count += 1
    queue.append((nx, ny))
    visited[nx][ny] = 1

return count

나머지 부분은 발전기와 코드가 전부 같고, 이 부분만 아주 살짝 다르다.

개수도 세줘야 하기 때문에, count에 1을 더해준다.

그리고 현재 값이 입력받은 건물의 유형(value)과 같은지도 판단해야 한다.

count를 더하든, 좌표를 append하든, 방문 여부를 확인하든, 전부 조건문 안에서 실행해야 한다.

그렇지 않고 popleft()를 할 때, 실행한다면, 중복 방문 가능성이 있어 TLE나 MLE가 뜰 수 있다.

# ---------- Main ----------
visited = [[0] * length for _ in range(length)]
apartment = [[i, 0] for i in range(31)]

건물(apartment) 유형 최댓값은 30이기에, 총 31개의 [i, 0]의 2차원 list를 선언한다.

31개로 선언한 이유는, 건물 유형 번호를 index 그대로 사용하기 위해 0 더미 데이터를 추가했다.

[i, 0]으로 추가한 이유는, i는 건물 유형, 0은 몇 개의 단지가 있는지 세기 위함이다.

# ---------- Main ----------
for r in range(length):
    for c in range(length):
        if BFS(r, c, graph[r][c]) >= K:
            apartment[graph[r][c]][1] += 1

apartment = sorted(apartment, key=lambda x: (-x[1], -x[0]))      
print(apartment[0][0])

이중 반복문으로 든 요소를 하나씩 검사한다.

BFS의 value에 해당하는 인자가 graph[r][c]이다. 즉 건물 유형 번호이다.

탐색을 돌면서, 해당 건물 유형 번호를 가진 개수가 K개 이상이라면, 1을 더해준다.

그리고 lambda식을 활용해 정렬을 해준다.

코드에서 필요한 정렬 기준은 두 가지이다. 하나는 가장 많은 단지, 다른 하나는 더 큰 건물 유형 번호.

x가 있을 때, 0번째 index는 유형 번호를 담고 있고, 1번째 index는 단지 수를 담고 있다.

그럼 1번째를 기준으로 먼저 내림차순 정렬을 하고, 다음으로 0번째를 기준으로 내림차순 정렬을 한다.

Python의 sort()와 sorted()는 stable sort이기 때문에, 두 번째 기준으로 값이 섞일 우려를 덜 수 있다.

정렬까지 완료하고 나면, 가장 첫 번째 행의 첫 번째 열 값이 정답이 된다.

구름톤 챌린지 3주, 12일차 문제 발전기이다.

4방위로 탐색을 하면서 이어진 공간이 몇 개인지 물어보는 아주 기본적인 DFS, BFS 문제이다.

백준에서 2606 바이러스, 2677 단지 번호 붙이기, 1012 유기농 배추 등이 있다.

from collections import deque

def BFS(x, y):
    if graph[x][y] == 0:
        return False
        
    global graph
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    queue = deque()
    queue.append((x, y))
    graph[x][y] = 0
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < length and 0 <= ny < length and graph[nx][ny]:
                queue.append((nx, ny))
                graph[nx][ny] = 0        
    
    return True


length = int(input())
graph = [list(map(int, input().split())) for _ in range(length)]

answer = 0    
    
for x in range(length):
    for y in range(length):
        if BFS(x, y):
            answer += 1
            
print(answer)

우선 DFS가 아닌 BFS로 풀었다.

그 이유는 N 최댓값이 1000이고, 그럼 마을의 최대 칸 수는 백만이 된다.

Python의 재귀 최대 깊이 default는 1000으로, BFS를 선택했다.

answer = 0

for x in range(length):
    for y in range(length):
        if BFS(x, y):
            answer += 1
            
print(answer)

2차원의 모든 요소를 하나씩 확인하면서 BFS를 수행한다.

만약 BFS 결과가 참이라면, 하나라도 집이 있는 것이니 answer를 1 증가한다.

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

Python에서는 deque 자료구조로 queue를 구현한다.

queue 라이브러리가 따로 있지만, 그건 애초에 멀티쓰레드 목적으로 만들었기 때문에 느리다.

상하좌우를 이동한 방향 값 dx, dy를 선언한다.

def BFS(x, y):
    if graph[x][y] == 0:
        return False
    
    global graph
    
    queue = deque()
    queue.append((x, y))
    graph[x][y] = 0
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < length and 0 <= ny < length and graph[nx][ny]:
                queue.append((nx, ny))
                graph[nx][ny] = 0        
    
    return True

나머지는 백준이든, 구름이든 dx와 dy를 사용한 이동을 알고 있다면 쉽게 해결 가능하다.

queue에 현재 좌표를 넣고, 방문 여부 확인을 위해 값을 0으로 바꿔준다.

popleft()로 가장 왼쪽 값을 뺴내어, 상하좌우 4방위를 확인한다.

그 좌표가 범위 내에 있으면서 아직 가보지 않았다면, queue에 추가하고 방문 여부 확인(0)을 해준다.

(이번 주에 대한 전체적인 리뷰와 의견은 5일차 해설까지 나오고나서 추후에 작성 예정)

구름톤 챌린지 3주, 11일차 문제인 통증 (2)이다.

기존에 있던 통증 문제를 동적 계획법으로 풀게끔 제출한 문제다.

이 문제와 굉장히 유사한 문제가 백준에 있다. 2839번 설탕 배달 문제이다.

구름에서는 A와 B이고, 백준에서는 3과 5라는 차이점이다.

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

result = 0

while N > 0:
    if N % B == 0:
        result += N // B
        break
        
    N -= A
    result += 1
    
print(-1) if N < 0 else print(result)

놀랍게도 이 문제도 그리디로 풀 수 있다. 반만...그리디?라고 해야 하나. 

그리디 알고리즘은 '매 선택 현재 상황에서 가장 최선의 선택을 하는 방법'이라, 완전한 그리디라고 할 수는 없다.

이 문제 조건과 바라는 사항은 여전히 똑같다.

정해진 개수의 물약을 사용하고, 가장 적게 사용하길 원한다.

가장 적게 사용한다는 것은, 가장 용량이 큰 물약을 가장 많이 사용해야 한다는 말과 같다.

N이 있을 때, B로 나누어 떨어진다면? A의 개수는 굳이 확인하지 않아도 된다.

A가 아니라 B라고 특정한 이유는, 문제 조건에 나와있다. B가 A보다 크다고.

하지만 B로 나눌 수 없다면, A를 최소한 1개만큼 사용한다는 이야기이다.

이때 A는 최소한 1개지, 몇 개를 사용할 지 모른다. 그럼 하나씩 빼보면 된다(N -= A; result += 1).

N이 0보다 클 때, 즉 통증이 아직 남아있다면(while N > 0) 계속해서 검사한다.

만약 0보다 작아진다면 자연스레 만들 수 없는 경우이다(print(-1)).

B로 나누어 떨어진다면(N % B == 0), 그만큼 더해주고(result += N // B), 계산 끝이다.