9:30 ~
어제 풀었던 내용을 복기했다. 오늘은 시험 전날이기 때문에 문제 푸는 것에 집중해보겠다.
14번 18352 특정 거리의 도시 찾기
https://www.acmicpc.net/problem/18352
도시와 도로의 개수가 주어지면 최단 거리 기준 K인 도시가 무엇인지 뽑는 문제이다. 만약에 도달할 수 있는 도시가 없다면 -1을 출력한다. BFS로 한 단계식 탐색하며 찾다가 K 거리에 도달하면 결과를 저장한다. 그래프 리스트로 도시들을 관리하고 거리 리스트로 -1로 초기화해 거리를 저장한다. 큐를 통해 도시를 탐색하고 거리를 갱신한다.
import sys
from collections import deque
input = sys.stdin.readline
# 도시 개수(N), 도로 개수(M), 거리 정보(K), 출발 도시(X) 입력
N, M, K, X = map(int, input().split())
# 그래프 초기화 (인접 리스트 방식)
graph = {i: [] for i in range(1, N+1)}
# 간선 정보 입력받기
for _ in range(M):
A, B = map(int, input().split())
graph[A].append(B) # 단방향 그래프이므로 a -> b만 저장 받음
distance = [-1] * (N + 1) # 모든 도시까지의 최단 거리 리스트 (초기값 -1 그래야 갱신가능)
distance[X] = 0 # 출발 도시의 거리는 0, X가 출발 도시이므로
queue = deque([X]) # BFS 구현 (큐 사용) 시작점 큐에 추가
while queue: # 큐가 빌 때 까지 수행
current = queue.popleft() # 현재 탐색 중인 도시
for next_city in graph[current]: # 연결된 도시들 확인
# current(0등)에서 이동할 수 있는 도시(next_city)를 찾음
if distance[next_city] == -1: # 방문하지 않은 도시라면
distance[next_city] = distance[current] + 1 # 거리 갱신
# 현재 도시에서 다음 도시까지 거리가 1이므로 +1을 해준다.
queue.append(next_city) # 큐에 추가
# 결과 출력 (N개의 도시에서 거리 K인 도시 찾기)
result = [i for i in range(1, N+1) if distance[i] == K]
# 결과가 없으면 -1 출력, 있으면 정렬 후 출력
if result:
for city in sorted(result): # 도시를 오름차순으로 출력
print(city)
else:
print(-1) # 결과 없다면 -1 출력도시와 도로의 개수가 주어지면 최단 거리 기준 K인 도시가 무엇인지 뽑는 문제이다. 만약에 도달할 수 있는 도시가 없다면 -1을 출력한다. BFS로 한 단계식 탐색하며 찾다가 K 거리에 도달하면 결과를 저장한다. 그래프 리스트로 도시들을 관리하고 거리 리스트로 -1로 초기화해 거리를 저장한다. 큐를 통해 도시를 탐색하고 거리를 갱신한다.
16번 2665 미로 만들기
https://www.acmicpc.net/problem/2665
미로에서 1은 갈 수 있는 칸이고 0은 갈수 없다. 1,1에서 최종목적지까지 몇번째 칸을 지나야 최종 목적지 갈 수 있는지 알아내는 문제이다. BFS와 다익스트라 방식으로 풀 수 있다.
import sys
import heapq
input = sys.stdin.readline
# 입력 받기
N = int(input().strip()) # 방의 크기
graph = [list(map(int, list(input().strip()))) for _ in range(N)] # 미로 입력
# 방향 이동 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 방문 처리 및 최소 비용 저장 (INF로 초기화)
INF = float('inf')
cost = [[INF] * N for _ in range(N)]
cost[0][0] = 0 # 시작점은 바꾸지 않으므로 비용 0
# 다익스트라를 위한 우선순위 큐 사용
pq = []
heapq.heappush(pq, (0, 0, 0)) # (비용, x좌표, y좌표) 비용이 작은 순으로 탐색
# 힙큐가 없을 때까지
while pq:
curr_cost, x, y = heapq.heappop(pq) # 현재 비용이 가장 작은 위치를 가져옴
# 이미 저장된 값보다 크다면 무시(최단 거리 구하므로)
if curr_cost > cost[x][y]:
continue
# 네 방향 탐색
for i in range(4):
nx, ny = x + dx[i], y + dy[i] # x 좌표 상하이동, y 좌표 좌우이동
if 0 <= nx < N and 0 <= ny < N: # 정해진 N 범위 내에 있는 경우
new_cost = curr_cost + (1 if graph[nx][ny] == 0 else 0) # 검은 방이면 +1
# 현재값 + (이동한 그래프 좌표가 0(검은방)이면 1반환, 그외에는 0반환)
# 기존 비용보다 새로운 비용이 더 적으면 갱신(검은방을 바꾸는 최소 비용을 찾음)
if new_cost < cost[nx][ny]:
cost[nx][ny] = new_cost # 구한 값은 cost에 입력(갱신)
heapq.heappush(pq, (new_cost, nx, ny)) # 우선순위 큐에 삽입(다른 경우 수 확인)
# 도착지점의 최소 변경 횟수 출력
print(cost[N-1][N-1]) # N이 8이더라도 좌표상 7,7이므로 N-1을 한다.기존의 BFS를 사용하면 금방 작성할 줄 알았는데 생각보다 오래걸렸다 이 문제가 검은 방을 만났을때 처리할 방법에 대해 궁금했는데, BFS랑 다익스트라랑 같이 써서 전체의 비용을 조사하면서 제일 작은 값을 계속 갱신하여 최솟값을 구한다는 생각이 키포인트인 것 같다. 코드도 난해해서 이해를 좀 더 해봐야겠다.
17번 7569 토마토
https://www.acmicpc.net/problem/7569
인풋값이 왜 저렇게 되는지 의문이었는데, 2번째 입력이 박스가 두개라서 위에 3줄, 아래 3줄이 다 다른 박스이다. 푸는 과정은 입력값을 3차원 리스트에 저장, 익은 토마토를 모두 큐에 넣고 BFS 탐색 BFS로 상하좌우위아래 돌면서 익힘 모든 토마토가 익었는지 확인하고 최소 날짜 출력한다.
from collections import deque
import sys
# 입력 받기 (빠른 입력 사용)
input = sys.stdin.read
data = input().split()
# 방향 벡터 (6방향: 상, 하, 좌, 우, 위, 아래)
# 상자 수가 있기 때문에 위, 아래 개념이 추가된다.
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]
# 데이터 파싱
M, N, H = map(int, data[:3]) # data의 첫 세값은 가로(M), 세로(N), 높이(H)
box = [] # 박스 리스트 생성
index = 3 # 실제 토마토상태 기록을 시작하는 위치이다.
queue = deque()
### 3차원 배열 만들기(H,N,M 순)
for h in range(H): # 층 저장
floor = []
for n in range(N): # 세로 저장
row = list(map(int, data[index:index + M])) # 행 구현
for m in range(M): # 가로 저장
if row[m] == 1: # 행 인덱스 1부터 저장
queue.append((h, n, m)) # 익은 토마토 위치를 큐에 저장
index += M # 다음 가로로 이동
floor.append(row) # 층에 행을 추가
box.append(floor) # 박스에 층을 추가
# BFS 수행
def bfs():
while queue:
z, x, y = queue.popleft()
for i in range(6):
nz, nx, ny = z + dz[i], x + dx[i], y + dy[i] # 근처 스캔(익힘)
if 0 <= nz < H and 0 <= nx < N and 0 <= ny < M and box[nz][nx][ny] == 0: # 제한되는 범위안이라면
box[nz][nx][ny] = box[z][x][y] + 1 # 날짜 증가
queue.append((nz, nx, ny)) # 큐에 날짜 추가
# BFS 실행
bfs()
# 결과 계산
max_days = 0 # 최고 날짜 0으로 초기화
for h in range(H):
for n in range(N):
for m in range(M):
if box[h][n][m] == 0: # 익지 않은 토마토가 남아있다면 -1 출력
print(-1)
exit()
max_days = max(max_days, box[h][n][m])
# 익지 않은 토마토가 남아있는게 아니면 최대날짜 출력
# 최소 일수는 (최댓값 - 1) (초기값이 1이었으므로)
print(max_days - 1 if max_days > 1 else 0)여기는 3차원 배열 만드는 것 자체가 어렵다. 시간이 없는 관계로 다음 문제로 넘어가곘다. 추후에 공부할 예정이다.
18번 3055 탈출
https://www.acmicpc.net/problem/3055
이동할 수 있는 곳: ., 물차있는 곳: * 비버굴: D, 고슴도치 위치: S 물과 고슴도치는 십자가로 움직인다. 그래서 BFS를 쓴다. 돌은 물과 고슴도치가 지나갈 수 없다.
from collections import deque
import sys
input = sys.stdin.read
data = input().split()
# 방향 벡터 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 입력값 처리
R, C = map(int, data[:2]) # R: 행 개수, C: 열 개수
index = 2 # 입력값 리스트에서 지도 데이터의 시작 인덱스(앞의 행과 열 개수 제외)
# 지도 (2차원 리스트) 및 큐 초기화
grid = [] # 지도 저장
water_queue = deque() # 물 BFS를 위한 큐
hedgehog_queue = deque() # 고슴도치 BFS를 위한 큐
for r in range(R):
row = list(data[index]) # 한 줄씩 읽어서 리스트로 변환
for c in range(C):
if row[c] == 'S': # 고슴도치 시작 위치 저장
hedgehog_queue.append((r, c, 0)) # (행, 열, 현재 이동 시간)
elif row[c] == '*': # 물의 위치 저장
water_queue.append((r, c)) # (행, 열)
grid.append(row)
index += 1 # 다음 줄로 이동
# BFS 수행 (물을 먼저 퍼뜨린 후 고슴도치 이동)
def bfs():
while hedgehog_queue: # 고슴도치가 이동할 곳이 없을 때까지 반복
# 1. 물을 먼저 확장
water_len = len(water_queue)
for _ in range(water_len): # 현재 큐에 있는 모든 물 확장
wx, wy = water_queue.popleft()
for i in range(4): # 상하좌우 탐색
nx, ny = wx + dx[i], wy + dy[i]
if 0 <= nx < R and 0 <= ny < C and grid[nx][ny] == '.': # 빈 공간일 경우
grid[nx][ny] = '*' # 물이 퍼짐
water_queue.append((nx, ny)) # 새로운 물 위치 큐에 추가
# 2. 고슴도치 이동
hedgehog_len = len(hedgehog_queue)
for _ in range(hedgehog_len): # 현재 큐에 있는 모든 고슴도치 이동
hx, hy, time = hedgehog_queue.popleft()
for i in range(4): # 상하좌우 탐색
nx, ny = hx + dx[i], hy + dy[i]
if 0 <= nx < R and 0 <= ny < C:
if grid[nx][ny] == 'D': # 비버의 굴에 도착한 경우
print(time + 1) # 걸린 시간 출력
return
if grid[nx][ny] == '.': # 빈 공간으로 이동 가능
grid[nx][ny] = 'S' # 방문 처리
hedgehog_queue.append((nx, ny, time + 1)) # 이동 정보 추가
# 고슴도치가 비버의 굴까지 갈 수 없는 경우
print("KAKTUS")
# BFS 실행
bfs()어떤 식으로 전개할지는 이해했지만, 코드는 100퍼센트 이해하진 못했다. 솔직히 복습이 우선이라 생각해서 복습을 하고 나중에 이해하겠다.
20번 2252 줄 세우기
https://www.acmicpc.net/problem/2252
N 명의 학생을 M만큼 비교해서 줄세운 결과를 출력하면 된다. 위상정렬로 순서를 나타내면 된다. 특성상 답이 여러개 있는데 아무거나 출력할 수 있다. 위상정렬을 구현해서 풀면된다. 주요 포인트는 디그리를 관리하는 리스트와 정점와 간선을 관리하는 리스트가 있어야한다. 큐에 디그리가 0인 정점을 저장하고 결과로 보내고, 빠진 정점은 자식 노드의 디그리를 -1하여 해당 과정을 반복하여 위상정렬을 수행한다.
import sys
input = sys.stdin.readline
from collections import deque
# 노드의 개수와 간선의 개수를 입력 받기
N, M = map(int, input().split())
# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (N + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
# 노드 갯수 N만큼 리스트 만든다
graph = [[] for i in range(N + 1)]
# 방향 그래프의 모든 간선 정보를 입력 받기
for _ in range(M):
A, B = map(int, input().split())
graph[A].append(B) # 정점 A에서 B로 이동 가능
# 진입 차수를 1 증가(A가 부모고 B가 자손이므로)
indegree[B] += 1
# 위상 정렬 함수
def topology_sort():
result = [] # 알고리즘 수행 결과를 담을 리스트
q = deque() # 큐 기능을 위한 deque 라이브러리 사용(디그리가 0인 정점 저장)
# 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
for i in range(1, N + 1):
if indegree[i] == 0:
q.append(i)
# 큐가 빌 때까지 반복
while q:
# 큐에서 원소 꺼내기
now = q.popleft() # 디그리 0인 정점 빼서 결과에 넣음
result.append(now)
# 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
for i in graph[now]:
indegree[i] -= 1
# 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
if indegree[i] == 0:
q.append(i)
# 위상 정렬을 수행한 결과 출력
for i in result:
print(i, end=' ')
topology_sort()위상 정렬 함수를 위에 식이 아니라 다른 식을 써봤는데 생각보다 인풋 넣기가 쉽지 않았고 GPT도 이상하게 알려줘서 다른 위상정렬 코드를 가져와 풀었다. 앞으로도 이 코드를 활용하여 작성해보겠다.
21번 2637 장난감 조립
https://www.acmicpc.net/problem/2637
각각의 부품이 요구되는 부품이 있다. 그래서 기본부품 1,2,3,4의 갯수를 구하면 되는 문제인데, 이걸 어떻게 위상 정렬로 풀어나가야할지 모르겠다... 문제가 사이클이 없고 시작과 종료 지점이 명확하여 위상정렬로 푼다고 한다. 각 부품들이 몇의 가중치로 만들어지는지 그림을 그려보면 이해하기 쉽다. 그러면 디그리가 0인 부품을 큐에 넣어서 필요한 부품을 리스트에 넣습니다. 가중치에 전에 있던 가중치를 곱해서 완성품까지 필요한 부품수를 추출합니다.
import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
M = int(input())
connect = [[] for _ in range(N + 1)] # N까지 간선 정보
need = [[0] * (N+1) for _ in range(N + 1)] # 필요한 부품수
q = deque() # 위상정렬 실행
degree = [0] * (N+1) # 진입 차수 0으로 초기화
for _ in range(M):
X, Y, K = map(int, input().split())
connect[Y].append((X, K)) # 자식과 가중치로 추가
degree[X] += 1 # X 디그리는 1씩 추가
for i in range(1, N + 1):
# 인디그리 0인걸 큐에 추가
if degree[i] == 0:
q.append(i)
while q: # 큐 내용 소진시 까지 실행
now = q.popleft() # 큐에서 왼쪽부터 차례대로 내보냄
# 현재 부품(now)을 이용하여 만들 수 있는 부품들 탐색
for next, next_need in connect[now]: # next: 다음 단계 부품 번호, next_need: 현재 부품이 몇 개 필요한지
# 현재 부품이 "기본 부품"인 경우
if need[now].count(0) == N + 1: # need[now] 리스트가 모두 0이라면, 즉 기본 부품이라면
need[next][now] += next_need # 기본 부품의 개수를 직접 추가
# 현재 부품이 "중간 부품"인 경우
else:
for i in range(1, N + 1): # 1번부터 N번 부품까지 확인
need[next][i] += need[now][i] * next_need
# 현재 부품(now)을 만들기 위해 필요한 기본 부품 개수를 이용해 next 부품에 누적(곱함)
degree[next] -= 1 # 진입 차수 감소 (현재 부품을 사용했으므로 next 부품의 필요 조건이 하나 줄어듦)
if degree[next] == 0: # 만약 진입 차수가 0이 되었다면 (더 이상 기다릴 필요 없음)
q.append(next) # 큐에 추가하여 다음 단계에서 처리
# 출력단
for x in enumerate(need[N]): # need[N]에서 필요한 기본 부품 정보를 가져옴
if x[1] > 0: # 만약 해당 부품이 필요하다면(0보다 크다면)
print(*x) # 부품 번호와 개수를 출력(리스트 형식 빼고 숫자만 출력)블로그를 참조하며 직접 하나하나 클론 코딩하며 학습했다. 그림을 그려보며 이론을 이해하긴 했으나 행렬을 구현할 생각을 하지 못했다. 기존에 가중치 값에 곱해주므로써 각각의 기본 부품 값을 알 수 있는 것이 놀랍다. 솔직히 모든 코드가 이해된 건 아니라서 좀더 이해해보고 다음 문제로 넘어 가겠다. 저 중간에 현재 부품과 중간 부품 나눠서 판단하는 for문이 이해하기 좀 어렵다...
내일은 3주차 시험날이다. 아침에 각 개념별 대표문제를 풀어보고, 시험을 쳐보겠다.
