오늘이 만우절이라 그런지 뽑기 이벤트가 있었다.
어제 5번 문제를 다 풀고 노션에 정리를 안해서 정리를 하고 벨로그 정리한 다음, 오늘 퀴즈 내용인 다익스트라 알고리즘에 대해 다시 공부해보겠다.
5번 11724 연결 요소의 개수
https://www.acmicpc.net/problem/11724
해당 문제는 몇개의 그래프가 있는지 묻는 문제와 같다. M만큼 입력을 받는다. 리스트를 만들어서 그래프를 만들고 기존 그래프에 해당되지 않은 정렬이면, 그래프 하나 만들면서 count +1 한다. 재귀적으로 반복 후에 count만 내보낸다. 라는게 내 생각이다.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6) # 재귀 깊이 제한 증가
N, M = map(int, input().split())
graph = [[False] * (N+1) for _ in range(N+1)]
visited = [False] * (N+1)
for _ in range(M):
u, v = map(int, input().split())
graph[u][v] = True
graph[v][u] = True
def dfs(idx) :
global visited # 방문기록을 지역변수로 불러옴
visited[idx] = True # 정점의 방문기록 True
# print(idx, end = ' ') # 정점을 출력
for next in range(1, N+1) : # 인덱스 1부터 끝까지 순회하며 확인
if not visited[next] and graph[idx][next]: # 방문하지 않았고 간선이 존재하는 정점이라면
dfs(next) # dfs에 재귀적으로 입력
# 연결요소 카운팅
count = 0
for i in range(1, N+1):
if not visited[i]:
dfs(i)
count += 1
print(count)dfs를 구현하는 건 전 문제를 참고하여 구현했는데, 연결 요소 카운팅을 어떻게 해야되나 고민을 많이 했다. dfs 자체도 건드리고 방법을 강구하다가 gpt에 물어 봤더니 생각보다 간단했다. for문으로 전체 요소에 방문정보가 False가 있으면 dfs를 다시 한번 호출하며 카운트를 1 올리는 방법이었다.
번외 1753 최단경로
https://www.acmicpc.net/problem/1753
다익스트리 기법을 이해하기 좋은 문제라고 한다.
import sys
import heapq
INF = float('inf') # 무한대를 의미하는 값 설정
def dijkstra(V, E, start, edges):
# 그래프를 인접 리스트로 표현 (1번 노드부터 시작)
graph = {i: [] for i in range(1, V + 1)}
for u, v, w in edges:
graph[u].append((w, v)) # u라는 기준점에서 (가중치, 목적지 노드)형태로 값 저장
# 최단 거리 테이블 초기화
distance = [INF] * (V + 1) # 모두 무한으로 초기화(그래야 비교해서 교체 가능, 0이면 안되므로)
distance[start] = 0 # 시작 정점의 거리는 0
# 우선순위 큐 (최소 힙) 사용
pq = [(0, start)] # (현재까지의 거리, 정점)
while pq:
cur_dist, cur_node = heapq.heappop(pq) # 최단 거리 노드 선택
if distance[cur_node] < cur_dist:
continue # 이미 처리된 노드라면 무시
# 현재 노드의 인접 노드 확인
for nxt_dist, nxt_node in graph[cur_node]:
new_dist = cur_dist + nxt_dist
if new_dist < distance[nxt_node]: # 더 짧은 경로 발견 시 갱신
distance[nxt_node] = new_dist
heapq.heappush(pq, (new_dist, nxt_node)) # 우선순위 큐에 추가
return distance
# 입력 받기
V, E = map(int, sys.stdin.readline().split()) # 정점 수 V, 간선 수 E
start = int(sys.stdin.readline()) # 시작 정점
edges = [tuple(map(int, sys.stdin.readline().split())) for _ in range(E)] # 간선 정보 입력
# 다익스트라 실행 및 결과 출력
distances = dijkstra(V, E, start, edges)
for i in range(1, V + 1):
print("INF" if distances[i] == INF else distances[i])
15번 1916 최소 비용 구하기
https://www.acmicpc.net/problem/1916
감이 안잡혀서 GPT의 도움을 받아 이해하고 코드를 분석했다.
- 시작 노드를 설정하고, 거리를 0으로 초기화 합니다.
- 우선 순위 큐를 사용하여 가장 짧은 거리를 가진 노드를 선택.
- 선택된 노드의 인접 노드들의 최단 거리를 갱신합니다.
- 모든 노드를 방문할 때까지 위 과정을 반복합니다.
import sys
import heapq
input = sys.stdin.readline # 빠른 입력
INF = int(1e9) # 무한대 값 (10억)
# 1. 입력 받기
N = int(input()) # 도시 (노드) 개수
M = int(input()) # 버스 (간선) 개수
# 2. 그래프 및 거리 테이블 초기화
graph = [[] for _ in range(N + 1)] # 인접 리스트 (1-based index)
distance = [INF] * (N + 1) # 최단 거리 테이블 (INF로 초기화)
# 3. 그래프 정보 입력 받기
for _ in range(M):
u, v, w = map(int, input().split()) # u에서 v로 가는 비용 w
graph[u].append((v, w)) # 방향 그래프 정점 u의 (정점v까지의, 가중치w)
# 4. 출발점과 도착점 입력 받기
start, end = map(int, input().split())
# 5. 다익스트라 알고리즘 (우선순위 큐 사용)
def dijkstra(start):
pq = [] # 우선순위 큐 (Min-Heap)
heapq.heappush(pq, (0, start)) # (비용, 시작점) 추가
distance[start] = 0 # 시작점 거리는 0으로 설정
while pq: # 큐가 빌 때까지 반복
dist, now = heapq.heappop(pq) # 현재 거리와 노드 번호 가져오기
if distance[now] < dist: # 이미 처리된 노드라면 무시
continue
# 현재 노드와 연결된 다른 노드 확인
for next_node, cost in graph[now]:
new_dist = dist + cost # 현재까지 거리 + 이동 비용 = 새 거리
if new_dist < distance[next_node]: # 더 짧은 경로 발견 시 갱신
distance[next_node] = new_dist
heapq.heappush(pq, (new_dist, next_node)) # 우선순위 큐에 추가
# 6. 다익스트라 실행
dijkstra(start)
# 7. 도착점까지의 최소 비용 출력
print(distance[end])거의다 이해는 됐는데, 코드 짜라고 하면 못짤 것 같아서 많은 반복 해야겠다...
3주차 퀴즈
3주차 퀴즈를 진행했다. 퀴즈를 풀면서 부족한 개념 부분을 추가했다.
개인적으로 내가 배운 부분에서 부족한 점을 뽑아봤다.
1. DFS 스택 내용 추가 학습(기존에는 행렬로 풀음)
2. B-Tree 디테일한 이론 및 내용 보강(기존에는 작동 방법만 어느정도 공부했음)
3. 운영체제 관점에서의 4가지 추상화 설명
6번 2606 바이러스
https://www.acmicpc.net/problem/2606
해당 문제는 dfs를 실행해서 감염된 컴퓨터 대수를 출력하면된다. dfs를 진행하다가 완료될텐데, 그때의 첫 컴퓨터가 연결된 노드만 알면되니까, 첫 dfs 재귀에서 연결된 노드정보만 받아오면 될 것 같다. 입력을 어떻게 받을지 몰라서 GPT를 참조 했다.
import sys
input = sys.stdin.readline
def dfs(graph, start_node): # dfs 구현부분
stack, visit = [],[] # 해당부분을 디렉토리로 안바꿔서 틀렸었다
stack.append(start_node) # 시작 노드를 스택에 먼저 입력한다.
while stack: # 스택에 사라질 때까지
node = stack.pop() # 스택에서 하나씩 pop한다.
if node not in visit: # 만약 방문하지 않은 노드라면
visit.append(node) # 노드를 방문했음을 표시하고
stack.extend(graph[node]) # 현재 노드와 연결된 노드를 스택에 추가한다
return visit
computer = int(input())
M = int(input())
graph = {i: [] for i in range(1, computer + 1)} # 참조한부분 어떻게 입력 받아야할지 몰라서
for _ in range(M): # 간선의 입력 받기
u,v = map(int, input().split())
graph[u].append(v) # 양방향으로 두 번
graph[v].append(u)
infected_computers = dfs(graph,1) # dfs를 1번부터 시작
print(len(infected_computers)-1) # 1번 컴퓨터를 제외한 총 길이 출력fs를 이미 들어간 값에 결과를 뽑아봤지,연결된 노드의 수를 뽑아야되서 고민을 했다. 근데 생각보다 간단하게 나온 노드의 수를 len으로 처리해서 쉽게 컴퓨터의 수를 얻을 수 있었다. dfs의 노드와 간선 입력값을 받는 방식을 새롭게 알게되었다.
7번 11725 트리의 부모 찾기
https://www.acmicpc.net/problem/2606
트리들이 구현되어 있을때, 각각 노드의 부모를 구하는 문제이다. DFS 돌려서 부모와 자식 관계 맞으면 부모정보를 내보내면된다. 이렇게 되기 위해서는 부모 리스트를 따로 관리해야되고 2부터 7까지 차례대로 출력되야해서 까다롭다.
import sys
input = sys.stdin.readline
def dfs(graph, start, N):
stack = [(start, 0)] # 스택 초기화 (현재 노드, 부모 노드)
parent_node = [0] * (N + 1) # 부모 노드 저장 리스트 (1-based index)
while stack:
node, parent = stack.pop() # 스택에서 현재 노드와 부모 노드 추출
if parent_node[node] == 0: # 아직 부모가 정해지지 않은 경우
parent_node[node] = parent # 현재 노드의 부모 저장
for next_node in graph[node]:
if parent_node[next_node] == 0: # 아직 방문하지 않은 노드만 추가
stack.append((next_node, node)) # (자식 노드, 부모 노드) 형태로 저장
return parent_node
N = int(input())
graph = {i:[] for i in range(1, N+1)}
for _ in range(N-1):
x,y = map(int, input().split())
graph[x].append(y)
graph[y].append(x)
result = dfs(graph, 1, N) # 루트 노드 1번으로 DFS 실행 result엔 부모노드 N값이 들어감
for i in range(2, N+1): # 2번 노드부터 부모 출력
print(result[i])난 기존 DFS에서 활용해서 답을 도출해낼 수 있을 줄 알았는데, 일부분이 바껴서 놀랐다. 자력으로 풀어보곘다고 시간투자좀 했는데, 첨부터 찾아볼걸 그랫나보다...
★★ 8번 1707 이분 그래프
https://www.acmicpc.net/problem/1707
이분 그래프가 무엇인지 모르겠고, 코드 작성에 어려움이 있어 블로그를 참고했습니다. 이분 그래프를 판단하기 위해서는 각 노드들을 이웃 노드들과 다른 색으로 계속 칠해 나가면서, 같은 색의 정점이 서로 연결되어 있는 모순이 발생하는지 여부를 확인하면 됩니다.
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
K = int(input()) # 테스트 케이스
def dfs(start, group):
global error # 에러처리를 전역 변수로 불러옴
# 만약 사이클이 true라면 재귀탈출
if error:
return
visited[start] = group # 해당 그룹으로 등록
for i in graph[start]:
if not visited[i]:
dfs(i, -group) # 다른 그룹으로 설정
elif visited[start] == visited[i]: # 인접한데 같은 그룹이라면
# 이분 그래프는 인접하고 다른 그룹이어야함
error = True # 에러값 True
return # 그후 재귀 리턴
for _ in range(K): # 테스트 케이스 만큼 반복
V, E = map(int, input().split()) # V:정점 개수, E:간선 개수
graph = [[] for _ in range(V + 1)] # 빈 그래프 생성
visited = [False] * (V + 1) # 방문한 정점 체크
error = False
for _ in range(E): # 입력된 값을 그래프에 추가(양방향)
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
for i in range(1, V + 1):
if not visited[i]: # 만약 아직 방문하지 않았다면
dfs(i, 1) # dfs를 돈다.
if error: # 만약 에러가 참이라면
break # 탈출
if error:
print("NO")
else:
print("YES")이 문제가 인풋이 복잡해서 어떻게 입력되고 그림으로 그려지는지 아는 것이 좋다. 직접해보며 왜 Yes와 No가 나오는지 알아야 풀 수 있다. 그렇다고 코드가 쉬운건 아니라서 오려운 문제라고 생각된다. 어느정도 이해하고 다음 문제로 넘어 가겠다.
★★ 9번 21606 아침 산책
https://www.acmicpc.net/problem/2606
이 문제는 이해부터 어렵다. 주요 요지는 중간에 있는 노드가 실내면 안된다는 것이다. 그러므로 실내/실외 노드끼리 직접 연결된 경우의 수를 찾고 이에따라 수식은 노드 k개 가능 경로수 = k*(k-1)/2 으로 유도할 수 있다.
# 이 문제는 이해부터 어렵다. 주요 요지는 중간에 있는 노드가 실내면 안된다는 것이다.
# 그러므로 실내/실외 노드끼리 직접 연결된 경우의 수를 찾고 이에따라 수식은
# 노드 k개 가능 경로수 = k*(k-1)/2 으로 유도할 수 있다.
import sys
sys.setrecursionlimit(10**6) # 재귀 깊이 제한 늘리기
def dfs(node, graph, A, visited):
"""
DFS를 통해 하나의 실외 컴포넌트와 연결된 실내 노드의 수를 세는 함수
node: 현재 탐색 중인 노드 (실외 노드)
graph: 그래프 정보
A: 각 노드의 실내/실외 정보
visited: 방문 여부 배열
return: 해당 실외 컴포넌트와 연결된 실내 노드의 수
"""
visited[node] = True
indoor_count = 0
for neighbor in graph[node]:
if A[neighbor-1] == '1': # 인접한 노드가 실내이면 카운트
indoor_count += 1
elif A[neighbor-1] == '0' and not visited[neighbor]: # 인접한 노드가 실외이고 아직 방문하지 않았으면 탐색 진행
indoor_count += dfs(neighbor, graph, A, visited)
return indoor_count
# 입력 처리
N = int(sys.stdin.readline().strip()) # 정점의 개수
A = sys.stdin.readline().strip() # 정점의 실내/실외 정보 (0: 실외, 1: 실내)
# 그래프 구성
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
u, v = map(int, sys.stdin.readline().split())
graph[u].append(v)
graph[v].append(u)
# 산책 경로 계산
answer = 0
# Case 1: 실내-실내 직접 연결
for i in range(1, N+1):
if A[i-1] == '1': # 실내 노드
for neighbor in graph[i]:
if A[neighbor-1] == '1': # 인접한 실내 노드
answer += 1
# Case 2: 실외 컴포넌트를 통한 실내-실내 연결
visited = [False] * (N+1)
for i in range(1, N+1):
if A[i-1] == '0' and not visited[i]: # 아직 방문하지 않은 실외 노드
indoor_nodes = dfs(i, graph, A, visited)
# 해당 실외 컴포넌트를 통해 연결될 수 있는 실내 노드 쌍의 개수 계산
answer += indoor_nodes * (indoor_nodes - 1)
# 산책 경로는 시작점과 도착점이 다른 경로이므로 양방향으로 각각 세어야 함
print(answer)
# 코드 설명
# 입력 처리:
# N: 정점의 개수
# A: 각 정점의 실내/실외 정보 (0: 실외, 1: 실내)
# 그래프 구성: 양방향 간선으로 그래프 만들기
# 실내-실내 직접 연결 계산:
# 모든 실내 정점에 대해, 인접한 다른 실내 정점과의 연결을 계산합니다.
# 이 경우 산책은 한 실내 정점에서 다른 실내 정점으로 바로 이동하는 것입니다.
# 실외를 통한 연결 계산:
# DFS를 사용하여 각 실외 컴포넌트(연결된 실외 정점들의 집합)를 탐색합니다.
# 각 실외 컴포넌트와 연결된 실내 정점의 수를 세고, 이를 이용해 가능한 경로 수를 계산합니다.
# 실내 정점 n개가 하나의 실외 컴포넌트와 연결되어 있다면, 그 사이의 가능한 경로 수는 n*(n-1)입니다.
# 최종 결과:
# 두 케이스에서 계산한 경로 수를 합하여 출력합니다.
# 산책은 방향이 있는 경로이므로 (A->B와A B->A는 다른 경로), 경로 수를 2로 나눌 필요가 없습니다.해당 문제의 전체적인 흐름은 이해됐다. 만약에 시간이 남으면 완벽히 이해해보겠다. GPT가 틀려서 claude 모델을 사용하여 답을 다시 구했다. 추후에 코드를 이해해 보겠다.
10번 14888 연산자 끼워넣기
https://www.acmicpc.net/problem/2606
주어진 숫자들이 있으면, 주어진 기호들 사용 횟수에 따라 식을 세우고 그 결과값중 최솟값과 최댓값을 구하면된다. 해당 문제가 난이도가 있어 해결 방법을 찾아보았는데, dfs와 백트래킹을 사용해서 재귀적으로 반복하며 최솟값과 최댓값을 구하면 된다고 한다.
N = int(input()) # 수의 개수 N 입력
data = list(map(int, input().split())) # 숫자들 입력
add, sub, mul, div = map(int, input().split()) # 연산자별 수 입력
# 최댓값과 최솟값 초기화(무한대로해서 비교를 하기 위함이다.)
max_value = -1e9
min_value = 1e9
# dfs로 모든 경우의 수 탐색
def dfs(i, arr): # i는 현재 진행 중인 수열의 인덱스, arr은 주어진 수 배열
global add, sub, mul, div, max_value, min_value # 지역변수 호출
# 주어진 수열을 다 받았을 경우 최댓값과 최솟값 계산
if i == N: # i가 수의 개수 N과 같으면
max_value = max(max_value, arr) # 기존 값이랑 현재 arr값중 더 큰것 반환
min_value = min(min_value, arr) # 기존 값이랑 현재 arr값중 더 작은것 반환
return
else:
# 더하기
if add > 0: # 0보다 크다면 실행
add -= 1 # 사용했으므로 대입해야되는 수 -1 후 실행
dfs(i+1, arr + data[i]) # 현재 값에 i 더하고 다음(i+1)숫자 재귀
add += 1 # 백트래킹을 위해 초기화
# 빼기
if sub > 0:
sub -= 1
dfs(i+1, arr - data[i])
sub += 1
# 곱하기
if mul > 0:
mul -= 1
dfs(i+1, arr * data[i])
mul += 1
# 나누기
if div > 0:
div -= 1
dfs(i+1, int(arr / data[i]))
div += 1
# DFS 메서드 호출
dfs(1, data[0])
# 여기서 1은 인덱스인데, 0으로 쓰면 연산자가 부족해지고 불필요한 연산을 해야하는 문제가 생긴다.
# 최댓값과 최솟값 출력
print(int(max_value))
print(int(min_value))
# int 처리를 안해서 틀렸다고 나왔는데, 상단에서 최댓값 최솟값이 무한대로 비교하면서 float자료형이라서
# 오답 처리가 된거였다. int 처리를 꼭해주자.문제 설명만 해석했을땐 코드를 어떻게 짜야할지 막막했는데, GPT를 통해 하나하나 살펴보니 어떤 로직으로 진행되고 백트래킹을 쓰는지 알게되었습니다.
마지막 부분에 최대/최소값이 무한대로 비교하면서 float형이므로 오류가 난다. 그러므로 int형으로 바꾸자.
13번 2178 미로 탐색
https://www.acmicpc.net/problem/2178
미로에서 1은 갈 수 있는 칸이고 0은 갈수 없다. 1,1에서 최종목적지까지 몇번째 칸을 지나야 최종 목적지 갈 수 있는지 알아내는 문제이다.
from collections import deque
import sys
input = sys.stdin.readline
def BFS(start_x, start_y, end_x, end_y, graph):
"""BFS를 사용하여 최단 거리를 탐색하는 함수"""
# 상하좌우 이동을 위한 방향 벡터를 설정합니다.
# dx, dy를 활용하면 for문을 돌며 이동 좌표를 한 번에 계산할 수 있습니다.
dx = [-1, 1, 0, 0] # 상, 하 이동
dy = [0, 0, -1, 1] # 좌, 우 이동
visited = set([(start_x, start_y)]) # 방문한 노드를 기록하는 집합 (x, y) 형태로 저장
# visited로 중복 방문을 방지
queue = deque([(start_x, start_y, 1)]) # (현재 위치 x, y, 이동 거리(1씩이동))
while queue: # 큐가 빌때까지 실행
x, y, steps = queue.popleft() # 현재 위치와 이동 거리 꺼내기
if x == end_x and y == end_y: # 도착 지점에 도달하면
return steps # 최단 거리 반환
for i in range(4): # 상하좌우 이동
nx = x + dx[i] # 현재 x에서 dx만큼 이동
ny = y + dy[i] # 현재 y에서 dy만큼 이동
# 범위를 벗어나지 않고 방문하지 않은 길(1)인 경우 이동
if 0 <= nx < N and 0 <= ny < M: # 입력된 N, M에 따라 범위를 벗어나지 않게 한다.
if (nx, ny) not in visited and graph[nx][ny] == 1: # 방문하지 않았고 1인 지역이면
visited.add((nx, ny)) # 방문 기록 추가
queue.append((nx, ny, steps + 1)) # 이동 거리 증가하여 추가
return -1 # 도착점까지 도달할 수 없는 경우
# 입력 처리
N, M = map(int, input().split()) # 미로 크기 입력
graph = [list(map(int, list(input().strip()))) for _ in range(N)] # 미로 정보 (숫자로 변환)
# BFS 실행 및 결과 출력
print(BFS(0, 0, N-1, M-1, graph)) # (0,0)에서 (N-1,M-1)까지 최단 거리 탐색
# N이 4라고 하면 인덱스로는 3까지라서 N-1을 한다.BFS의 제일 기초문제인데도 코드 해석하는데 오랜시간이 걸렸다. DFS랑 다르게 위와 같은 2차원 배열에서는 처리하기가 굉장히 어려운 것 같다. 오늘은 3시경까지 공부하느라 늦어서 내일 아침에 다시한번 이해하겠다. 앞으로는 위의 식을 활용하여 여러 BFS 문제를 풀어보겠다.
