0. 서문
내일이 시험일이다. 시험을 보기 전 지금까지 풀어본 문제를 다시 풀어본 김에 블로그에 올리지 않은것들 (거의 대부분의 것들을 올리지 않았다) 를 올리려 한다.
1.DFS와 BFS
https://www.acmicpc.net/problem/1260
DFS 와 BFS 를 익히기 좋은 가장 기초적인 문제였다.
그다지 특별한것은 없었으나 DFS 와 BFS의 경우 구현하고자 한다면 방법은 달라도 구조 자체는 거의 동일하니 외우기 위한 목적으로 하루에 한번씩은 해보면 어떨까 싶은 생각이 드는 문제였다.
from collections import deque
import sys
input = sys.stdin.readline
def dfs(v):
visited[v] = True
print(v, end=" ")
for i in arr[v]:
if not visited[i]:
dfs(i)
def bfs(v):
que = deque([v])
visited[v] = True
while que:
x = que.popleft()
print(x, end=" ")
for i in arr[x]:
if not visited[i]:
que.append(i)
visited[i] = True
n, m, v = map(int, input().split())
arr = [[]for _ in range(n+1)]
visited = [False] * (n+1)
for _ in range(m):
a, b = map(int, input().split())
arr[a].append(b)
arr[b].append(a)
for i in range(1, n+1):
arr[i].sort()
dfs(v)
print()
visited = [False] * (n+1)
bfs(v)2.연결 요소의 개수
https://www.acmicpc.net/problem/11724
추후, 빙산을 풀때 이것을 생각하여 접근하였으나 생각되로 되지 않아 어려웠던것이 기억난다.
DFS를 통하여 연결된것을 파악하기 때문에 DFS 가 돌아갈때마다 cnt 를 +1 해주는 방식으로 연결 요소의 개수를 파악하는식으로 접근하였다.
import sys
sys.setrecursionlimit(10 ** 4)
input = sys.stdin.readline
def dfs(v):
visited[v] = True
for i in arr[v]:
if not visited[i]:
dfs(i)
n, m = map(int, input().split())
arr = [[] for _ in range(n+1)]
visited = [False] * (n+1)
cnt = 0
for _ in range(m):
a, b = map(int, input().split())
arr[a].append(b)
arr[b].append(a)
for i in range(1, n+1):
arr[i].sort()
for i in range(1, n+1):
if not visited[i]:
dfs(i)
cnt += 1
print(cnt)3. 바이러스
위의 연결 요소의 개수와 비슷한 방식으로 접근하게 된 문제였다. 다만, 연결 요소의 개수는 DFS 가 돌아갈때 cnt 를 + 1 씩 해주었다면 바이러스의 경우는 1과 연결된 컴퓨터의 개수를 새어야 하기 때문에 DFS 를 1 로 시작하여 돌면서 cnt 를 +1 씩 해주는것으로 바이러스에 감연된 컴퓨터의 개수를 파악하는 식으로 접근하여 해결하였다.
import sys
sys.setrecursionlimit(10 ** 4)
input = sys.stdin.readline
def dfs(v):
global cnt
visited[v] = True
for i in arr[v]:
if not visited[i]:
cnt += 1
dfs(i)
n = int(input())
m = int(input())
arr = [[] for _ in range(n+1)]
visited = [False] * (n+1)
cnt = 0
for _ in range(m):
a, b = map(int, input().split())
arr[a].append(b)
arr[b].append(a)
for i in range(1, n+1):
arr[i].sort()
dfs(1)
print(cnt)4. 미로 탐색
https://www.acmicpc.net/problem/2178
이런 유형의 문제가 나오면 바로 dx, dy 부터 만들게 되는 습관이 생겼다. 보자마자 든 생각은 일단 그리디 알고리즘 쪽인것같다는 생각이 들었다. 다만, 실제로 알고리즘 분류를 보디 그리디는 아니었다. 다시 생각해보면 그냥 예시가 1일때 따라가면 바로 답이 나오도록 되어있었어서 그렇게 생각한게 아닌가 싶다.
BFS 를 통하여 풀었다.
import sys
from collections import deque
sys.setrecursionlimit(10 ** 4)
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline
def bfs(start, end):
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()
queue.append((start, end))
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = dx[i] + x, dy[i] + y
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if arr[nx][ny] == 0:
continue
if arr[nx][ny] == 1:
arr[nx][ny] = arr[x][y] + 1
queue.append((nx, ny))
return arr[n-1][m-1]
n, m = map(int, input().split())
arr = [list(map(int, input().rstrip())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
print(bfs(0, 0))
5. 특정 거리의 도시 찾기
https://www.acmicpc.net/problem/18352
import sys
from collections import deque
sys.setrecursionlimit(10 ** 4)
input = sys.stdin.readline
def bfs(start):
answer = []
que = deque([start])
visited[start] = True
distance[start] = 0
while que:
now = que.popleft() # 현재 위치
for i in city[now]:
if not visited[i]:
visited[i] = True
que.append(i)
distance[i] = distance[now] + 1
if distance[i] == k:
answer.append(i)
if len(answer) == 0:
print(-1)
else:
answer.sort()
for i in answer:
print(i, end='\n')
# 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X
n, m, k, x = map(int, input().split())
city = [[] for _ in range(n+1)]
visited = [False] * (n+1)
distance = [0] * (n+1)
for _ in range(m):
a, b = map(int, input().split())
city[a].append(b)
bfs(x)6. 트리의 부모 찾기
https://www.acmicpc.net/problem/11725
import sys
from collections import deque
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
def dfs(start, tree, parents):
for i in tree[start]:
if parents[i] == 0:
parents[i] = start
dfs(i, tree, parents)
n = int(input())
arr = [[] for _ in range(n+1)]
Parents = [0 for _ in range(n+1)]
for _ in range(n-1):
a, b = map(int, input().split())
arr[a].append(b)
arr[b].append(a)
dfs(1, arr, Parents)
for i in range(2, n+1):
print(Parents[i])
7. 이분 그래프
https://www.acmicpc.net/problem/1707
import sys
from collections import deque
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
def dfs(start, group):
visited[start] = group
for i in arr[start]:
if not visited[i]:
a = dfs(i, -group)
if not a:
return False
elif visited[i] == visited[start]:
return False
return True
n = int(input())
for _ in range(n):
v, e = map(int, input().split()) # 정점의 개수 V와 간선의 개수 E
arr = [[] for _ in range(v+1)]
visited = [False] * (v+1)
for _ in range(e):
a, b = map(int, input().split())
arr[a].append(b)
arr[b].append(a)
for i in range(1, v + 1):
if not visited[i]:
result = dfs(i, 1)
if not result:
break
print("YES" if result else "NO")
8. 연산자 끼워넣기
https://www.acmicpc.net/problem/14888
import sys
input = sys.stdin.readline
N = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split())) # +, -, *, //
maximum = -1e9
minimum = 1e9
def dfs(depth, total, plus, minus, multiply, divide):
global maximum, minimum
if depth == N:
maximum = max(total, maximum)
minimum = min(total, minimum)
return
if plus:
dfs(depth + 1, total + num[depth], plus - 1, minus, multiply, divide)
if minus:
dfs(depth + 1, total - num[depth], plus, minus - 1, multiply, divide)
if multiply:
dfs(depth + 1, total * num[depth], plus, minus, multiply - 1, divide)
if divide:
dfs(depth + 1, int(total / num[depth]),
plus, minus, multiply, divide - 1)
dfs(1, num[0], op[0], op[1], op[2], op[3])
print(maximum)
print(minimum)9. 최소비용 구하기
https://www.acmicpc.net/problem/1916
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
infinity = int(2e9)
def Dijkstra(start):
dp[start] = 0
heap = []
heappush(heap, [0, start])
while heap:
w, n = heappop(heap)
if dp[n] < w:
continue
for n_n, wei in arr[n]:
n_w = w + wei
if dp[n_n] > n_w:
dp[n_n] = n_w
heappush(heap, [n_w, n_n])
n = int(input())
m = int(input())
arr = [[] for _ in range(n+1)]
dp = [infinity for i in range(n+1)]
for i in range(m):
start_p, end_p, cost = map(int, input().split())
arr[start_p].append([end_p, cost])
start, end = map(int, input().split())
Dijkstra(start)
print(dp[end])10. 미로만들기
https://www.acmicpc.net/problem/2665
import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10 ** 4)
input = sys.stdin.readline
def find():
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
heap = []
heappush(heap, [0, 0, 0])
visit[0][0] = True
while heap:
a, x, y = heappop(heap)
if x == n - 1 and y == n - 1:
print(a)
return
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n and not visit[nx][ny]:
visit[nx][ny] = True
if board[nx][ny] == 0:
heappush(heap, [a + 1, nx, ny])
else:
heappush(heap, [a, nx, ny])
n = int(input())
board = [list(map(int, input().rstrip())) for _ in range(n)]
visit = [[False] * n for _ in range(n)]
find()
11. 탈출
https://www.acmicpc.net/problem/3055
import collections
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(input().strip()) for _ in range(n)]
distance = [[0] *m for _ in range(n)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
queue = collections.deque()
def bfs(Dx,Dy):
while queue:
x,y = queue.popleft()
if graph[Dx][Dy] == 'S':
return distance[Dx][Dy]
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if (graph[nx][ny] == '.' or graph[nx][ny] == 'D') and graph[x][y] == 'S':
graph[nx][ny] = 'S'
distance[nx][ny] = distance[x][y] + 1
queue.append((nx,ny))
elif (graph[nx][ny] =='.' or graph[nx][ny] =='S') and graph[x][y] == '*':
graph[nx][ny] = '*'
queue.append((nx,ny))
return "KAKTUS"
for x in range(n):
for y in range(m):
if graph[x][y] == 'S':
queue.append((x,y))
elif graph[x][y] == 'D':
Dx,Dy = x,y
for x in range(n):
for y in range(m):
if graph[x][y] == '*':
queue.append((x,y))
print(bfs(Dx,Dy))
좋은 프로그래머는 뭘까