2606. 바이러스
https://www.acmicpc.net/problem/2606
처음 풀어본 그래프 탐색 문제이며 DFS를 이용해 답을 구하였다.
import sys
input = sys.stdin.readline
def depth_first(graph, v, visited):
global cnt
visited[v] = True
for i in graph[v]:
if not visited[i]:
cnt += 1
depth_first(graph, i, visited)
N = int(input())
M = int(input())
graph = [[] for i in range(N + 1)]
for _ in range(M):
x, y = map(int, input().split())
graph[x].append(y)
graph[y].append(x)
visited = [False] * (N + 1)
cnt = 0
depth_first(graph, 1, visited)
print(cnt)아직 DFS 함수를 정의하는 것과 전역 변수 global을 사용하는 데에 어려움이 있다. 또한 어떤 유형의 문제에서 DFS를 사용해야 하는지 아직 잘 모르겠다.
1260. DFS와 BFS
https://www.acmicpc.net/problem/1260
import sys
from collections import deque
input = sys.stdin.readline
def depth_first(graph, v, visited):
visited[v] = True
graph[v].sort()
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
depth_first(graph, i, visited)
def breadth_first(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
graph[v].sort()
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
N, M, V = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
x, y = map(int, input().split())
graph[x].append(y)
graph[y].append(x)
visited1 = [False] * (N + 1)
visited2 = [False] * (N + 1)
depth_first(graph, V, visited1)
print()
breadth_first(graph, V, visited2)graph[v].sort()하는 것이 중요했다.
문제에서 요구하는 결과값의 형태로 출력하는 것이 쉽지 않았다.
11725. 트리의 부모 찾기
https://www.acmicpc.net/problem/11725
문제에서 주어진 각 노드의 부모를 출력하는 문제이다. DFS를 이용해 해당 노드를 방문하기 전에 어떤 노드로부터 파생되었는지를 결과에 담아 순서대로 출력하였다.
import sys
sys.stdin = open("11725_트리의 부모 찾기.txt", "r")
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
def depth_first(graph, v, visited):
global result
visited[v] = True
for i in graph[v]:
if not visited[i]:
result[i].append(v)
depth_first(graph, i, visited)
N = int(input())
graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
x, y = input().split()
graph[int(x)].append(int(y))
graph[int(y)].append(int(x))
visited = [[] for _ in range(N + 1)]
result = [[] for _ in range(N + 1)]
depth_first(graph, 1, visited)
for ans in result[2:]:
print(*ans)처음 답안을 제출했을 때 RecursionError라는 런타임 에러가 발생하였는데, sys.setrecursionlimit(10 ** 8) 설정을 통해 해결하였다.
2178. 미로 탐색
https://www.acmicpc.net/problem/2178
간선 간의 비용이 같은 경우에 최단 경로를 찾는 문제는 BFS를 이용해 문제를 해결한다.
import sys
from collections import deque
sys.stdin = open("2178_미로 탐색.txt", "r")
input = sys.stdin.readline
def breadth_first(x, y):
# 큐를 생성하고 시작점을 큐에 추가
queue = deque()
queue.append((x, y))
while queue:
# 큐에서 (x, y) 좌표를 확인
x, y = queue.popleft()
# (x, y)의 상하좌우를 탐색
for i in range(4):
# 기존 x값에 -1, 0, 1을 더한다
nx = x + dx[i]
# 기존 y값에 -1, 0, 1을 더한다
ny = y + dy[i]
# 새로운 좌표가 범위를 벗어나면 넘어간다
if nx < 0 or nx >= N or ny < 0 or ny >= M:
continue
# 새로운 좌표가 이동 불가능하면 넘어간다
if graph[nx][ny] == 0:
continue
# 새로운 좌표가 이동 가능하면 새로운 좌표로 이동
if graph[nx][ny] == 1:
# 새로운 좌표로 이동하며 이동 횟수를 1 추가
graph[nx][ny] = graph[x][y] + 1
# 새로운 좌표를 큐에 추가
queue.append((nx, ny))
# 목표 지점에 도착하기 까지의 총 이동 횟수를 출력
return graph[N - 1][M - 1]
N, M = map(int, input().split())
graph = []
for _ in range(N):
graph.append(list(map(int, input().rstrip())))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
print(breadth_first(0, 0))아직 풀이 과정이 이해가 되지 않아 답안 코드를 참고하였다. 다시 돌아와서 이해할 예정.
이해했다.
1987. 알파벳
먼저 DFS를 이용한 풀이는 시간 초과가 발생하였다.
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
def depth_first(x, y, cnt):
global answer
answer = max(answer, cnt)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < R and 0 <= ny < C and not visited[alphabet[nx][ny]]:
visited[alphabet[nx][ny]] = True
depth_first(nx, ny, cnt + 1)
visited[alphabet[nx][ny]] = False
R, C = map(int, input().split())
alphabet = []
for _ in range(R):
alphabet.append(list(map(lambda a: ord(a) - 65, input().rstrip())))
visited = [False] * 26
visited[alphabet[0][0]] = True
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
answer = 0
depth_first(0, 0, 1)
print(answer)BFS를 이용한 풀이를 통해 시간 제한을 통과하였다.
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
def breadth_first():
R, C = map(int, input().rstrip().split())
alphabet = [list(input()) for _ in range(R)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
answer = 0
queue = set()
queue.add((0, 0, 1, alphabet[0][0]))
while queue:
x, y, cnt, visited = queue.pop()
answer = max(answer, cnt)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < R and 0 <= ny < C:
if alphabet[nx][ny] not in visited:
queue.add((nx, ny, cnt + 1, visited + alphabet[nx][ny]))
return answer
print(breadth_first())1234. 도마도
https://www.acmicpc.net/problem/7569
import sys
from collections import deque
# sys.stdin = open("7569_도마도.txt", "r")
input = sys.stdin.readline
def breadth_first():
M, N, H = map(int, input().rstrip().split())
# 주어진 입력값을 3중 네스티드 리스트 형태로 입력
arr = [[list(map(int, input().rstrip().split())) for _ in range(N)] for _ in range(H)]
queue = deque()
# 익은 도마도가 위치한 좌표를 큐에 삽입
for i in range(H):
for j in range(N):
for k in range(M):
if arr[i][j][k] == 1:
queue.append((i, j, k, 0))
# 익은 도마도가 이동 가능한 여섯 개의 방향을 탐색
dm = [1, 0, 0, -1, 0, 0]
dn = [0, 1, 0, 0, -1, 0]
dh = [0, 0, 1, 0, 0, -1]
# 모든 도마도가 익기까지 걸린 시간
cnt = 0
while queue:
z, x, y, cnt = queue.popleft()
for i in range(6):
nm = y + dm[i]
nn = x + dn[i]
nh = z + dh[i]
# 이동 가능한 칸이 상자를 벗어나지 않고 익지 않은 도마도인 경우
if 0 <= nm < M and 0 <= nn < N and 0 <= nh < H and arr[nh][nn][nm] == 0:
# 새로운 칸으로 이동하여 도마도를 익게 함
arr[nh][nn][nm] = 1
# 소요 시간에 하루를 더하여 이동한 칸을 큐에 삽입
queue.append((nh, nn, nm, cnt + 1))
for i in range(H):
for j in range(N):
for k in range(M):
# 모든 도마도가 익을 수 없는 경우이면 -1을 출력
if arr[i][j][k] == 0:
return -1
# 모든 도마도가 익기까지 걸린 시간을 출력
return cnt
print(breadth_first())2252. 줄 세우기
https://www.acmicpc.net/problem/2252
위상 정렬이라는 개념을 이해하는 데에 도움이 되는 기초적인 문제이다.
import sys
from collections import deque
input = sys.stdin.readline
def topology_sort():
queue = deque()
result = []
for i in range(1, N + 1):
if degree[i] == 0:
queue.append(i)
while queue:
current = queue.popleft()
result.append(current)
for i in graph[current]:
degree[i] -= 1
if degree[i] == 0:
queue.append(i)
print(*result)
N, M = map(int, input().split())
degree = [0] * (N + 1)
graph = [[] for _ in range(N + 1)]
for _ in range(M):
A, B = map(int, input().split())
graph[A].append(B)
degree[B] += 1
topology_sort()3055. 탈출
https://www.acmicpc.net/problem/3055
물이 차있는 지역('*')과 고슴도치('S')를 한 개의 큐에 삽입하고 처리하는 것이 특히 어려웠던 문제. 풀이 과정을 이해하기 까지 정말 오래 걸렸다.
import sys
from collections import deque
# sys.stdin = open("3055_탈출.txt", "r")
input = sys.stdin.readline
def breadth_first():
R, C = map(int, input().split())
arr = [list(input().rstrip()) for _ in range(R)]
queue = deque()
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
# 물이 차있는 지역과 고슴도치를 큐에 삽입
for i in range(R):
for j in range(C):
# 해당 지역이 목표 지점인 경우
if arr[i][j] == 'D':
D = [i, j]
# 해당 지역이 물이 차있는 지역인 경우
elif arr[i][j] == '*':
queue.append([i, j, '*'])
# 해당 지역이 고슴도치의 위치인 경우
elif arr[i][j] == 'S':
arr[i][j] == 1
S = [i, j, 0]
queue.append(S)
while queue:
# z는 고슴도치를 큐에 삽입한다는 것과 이동 시간을 의미
x, y, z = queue.popleft()
# 목표 지점에 도착하면 z를 출력
if x == D[0] and y == D[1]:
print(z)
break
else:
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 이동하는 지역이 범위를 벗어나는 경우
if nx < 0 or nx >= R or ny < 0 or ny >= C:
continue
else:
# 이동하는 지역이 목표 지점, 물이 이미 차있는 지역과 바위가 아닌 경우
if z == '*' and arr[nx][ny] != 'D' and arr[nx][ny] != '*' and arr[nx][ny] != 'X':
arr[nx][ny] = '*'
queue.append([nx, ny, '*'])
# 이동하는 지역이 비어있는 곳이거나 목표 지점인 경우
elif type(z) == int and (arr[nx][ny] == '.' or arr[nx][ny] == 'D'):
arr[nx][ny] = z + 1
queue.append([nx, ny, z + 1])
# 큐가 빌 때까지 목표 지점에 도착하지 못하는 경우
if len(queue) == 0:
print("KAKTUS")
breadth_first()2294. 동전 2
https://www.acmicpc.net/problem/2294
import sys
from collections import deque
# sys.stdin = open("2294_동전 2.txt", "r")
input = sys.stdin.readline
N, K = map(int, input().split())
arr = set(int(input()) for _ in range(N))
# K원 이하의 값들에 대해 방문 처리
check = [0 for _ in range(K + 1)]
queue = deque()
for num in arr:
# 동전의 가치가 K원보다 크면 생략
if num > K:
continue
else:
queue.append([num, 1])
check[num] = 1
while queue:
# 동전의 가치를 누적한 합과 사용된 동전의 개수
sum, cnt = queue.popleft()
# 누적 합이 K원이라면 flag를 전환하고 사용된 동전의 개수를 출력
if sum == K:
print(cnt)
break
for num in arr:
if sum + num > K:
continue
# 누적 합에 동전을 더한 값에 대해 방문 처리
if check[sum + num] == 0:
check[sum + num] = 1
# 사용된 동전의 개수를 더하고 누적 합에 동전을 더한 값을 큐에 삽입
queue.append([sum + num, cnt + 1])
# 주어진 동전으로 K원을 만들 수 없는 경우 -1을 출력
if sum != K:
print(-1)2617. 구슬 찾기
https://www.acmicpc.net/problem/2617
새로 알게 된 defaultdict() 라이브러리를 사용하여 구슬의 무게를 비교하는 과정에서 용이하게 사용하였다.
defaultdict is a subclass of the built-in dict class. It overrides one method and adds one writable instance variable.
출처: https://docs.python.org/3/library/collections.html#collections.defaultdict
defaultdict()는 딕셔너리 value의 기본값을 설정할 수 있다.
import sys
from collections import defaultdict
# sys.stdin = open("2617_구슬 찾기.txt", "r")
input = sys.stdin.readline
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(M)]
result = 0
def depth_first(graph, v):
# 전역변수 global을 이용해 외부에서 선언한 변수 사용
global cnt
# v에 대해 방문 처리
visited[v] = True
# 방문하지 않은 v의 간선을 DFS 함수로 재귀
for i in graph[v]:
if not visited[i]:
cnt += 1
depth_first(graph, i)
return cnt
# defaultdict()는 딕셔너리 value의 기본값을 설정할 수 있다.
light = defaultdict(list)
heavy = defaultdict(list)
# 주어진 구슬 순서쌍 비교 정보를 리스트에 입력
for x, y in arr:
light[x].append(y)
heavy[y].append(x)
# 방문 처리를 기록하는 visited 생성
for i in range(1, N + 1):
visited = [False] * (N + 1)
# cnt 초기화
cnt = 0
# 전체 구슬의 절반 이상이 해당 구슬보다 가볍다면 중간 구슬이 될 수 없다.
if depth_first(light, i) >= (N + 1) // 2:
result += 1
# cnt 초기화
cnt = 0
# 전체 구슬의 절반 이상이 해당 구슬보다 무겁다면 중간 구슬이 될 수 없다.
if depth_first(heavy, i) >= (N + 1) // 2:
result += 1
print(result)
hello world