18352 특정 거리의 도시 찾기
📌문제 링크
https://www.acmicpc.net/problem/18352
💡 문제 풀이
한 도시에서 다른 도시들로 가는 최단거리를 구하는 거니까 다익스트라 알고리즘을 사용하면 되겠다고 생각했다
.......
근데 이번 주 주제가 BFS니까 일단 그걸로 풀어봐야지..
예전에 BFS로 최단거리 풀었던 기억을 최대한 끄집어내서 풀어봤다
- 도시 연결 정보가 들어있는 인접리스트 graph 배열
- 방문 정보를 표시하는 visited 배열
- 거리 정보를 저장하는 distance 배열
- bfs할 때 필요한 queue
이렇게 사용해서 풀었다!
📋코드
# 18352 특정 거리의 도시 찾기
import sys
from collections import deque
INF = int(1e9)
n, m, k, x = map(int, sys.stdin.readline().split())
# 도시 연결 인접리스트
graph = [[] for _ in range(n + 1)]
# 방문 표시
visited = [False for _ in range(n + 1)]
# 최단거리 저장
distance = [INF for _ in range(n + 1)]
# 도시 연결 정보 입력
for i in range(m):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
def bfs(start):
# 시작 도시, 거리 큐 삽입
# 출발 도시 x에서 출발 도시 x로 가는 최단 거리는 0이므로 거리 0으로 삽입
queue = deque([[start, 0]])
visited[start] = True
distance[start] = 0
while queue:
# 큐 pop
v, w = queue.popleft()
# 연결된 모든 도시에 대해
for i in graph[v]:
# 방문하지 않은 도시라면
if not visited[i]:
# 최단거리 갱신 (도로 가중치는 1)
distance[i] = min(w + 1, distance[i])
# 큐 삽입
queue.append([i, distance[i]])
visited[i] = True
bfs(x)
# 최단거리가 k인 도시가 있는지 검사
check = 0
for i in range(1, n + 1):
if distance[i] == k:
print(i)
check += 1
# 최단거리 k인 도시가 없다면 -1 출력
if check == 0:
print(-1)
14502 연구소
📌문제 링크
https://www.acmicpc.net/problem/14502
💡 문제 풀이
예전에 풀었던 게 어렴풋이 기억이 난다...
아마 벽 3개를 모든 경우의 수에 따라 무작위로 세워서 bfs를 해야했던 걸로 기억한다
풀이과정은 대략적으로 기억이 나긴 하는데 조금씩 헷갈려서 옛날 코드를 조금 참고해서 풀었다 ㅎㅎ..
옛날에 정리해놓은 풀이과정 링크
14502 연구소 풀이
📋코드
# 14502 연구소 다시풀기
import sys
import copy
from collections import deque
n, m = map(int, sys.stdin.readline().split())
# 연구소
graph = []
# 바이러스 위치
virus = []
# 상하좌우 이동
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
# 결과값
result = 0
# 연구소 입력
for i in range(n):
tmp = list(map(int, sys.stdin.readline().split()))
# 바이러스 위치 저장
for j in range(m):
if tmp[j] == 2:
virus.append([i, j])
graph.append(tmp)
# 바이러스 퍼뜨리기
def bfs():
tmp = copy.deepcopy(g)
queue = deque(virus)
while queue:
x, y = queue.popleft()
# 상하좌우 이동
for d in range(4):
nextX = x + dx[d]
nextY = y + dy[d]
if 0 <= nextX < n and 0 <= nextY < m:
if tmp[nextX][nextY] == 0:
tmp[nextX][nextY] = 2
queue.append([nextX, nextY])
zero = 0
# 안전영역(빈 칸) 세기
for _ in range(n):
zero += tmp[_].count(0)
# 더 큰 안전 영역의 넓이 저장
global result
result = max(result, zero)
return
# 벽 세우기
def make_wall(cnt):
if cnt == 3:
bfs()
return
for k in range(n):
for p in range(m):
if g[k][p] == 0:
g[k][p] = 1
make_wall(cnt + 1)
g[k][p] = 0
# 첫 번째 벽 세우기
for i in range(n):
for j in range(m):
if graph[i][j] == 0:
g = copy.deepcopy(graph)
g[i][j] = 1
make_wall(1)
g[i][j] = 0
print(result)
14888 연산자 끼워넣기
📌문제 링크
https://www.acmicpc.net/problem/14888
💡 문제 풀이
- 큐에 [start, n, op] 순서로 삽입한다
- start: 다음 연산할 숫자의 순서 (ex. 현재 i번째 숫자까지 연산했다면 start는 i + 1)
- n : 지금까지 연산한 결과값
- op : 남은 연산자 개수 배열
- 이 큐를 사용해서 bfs를 수행한다 (이게 제대로 된 bfs가 맞는지는 모르겠지만...)
- 모든 연산이 끝났을 때 즉, 모든 연산자 개수가 0일 때 최댓값과 최솟값을 갱신한다
- 개수가 남아있는 모든 연산자에 대해 연산자를 끼워넣고,
[start + 1, n 과 a[start]를 연산한 값, 갱신된 op]
순서로 큐에 삽입한다 (자세한 건 코드 참고..)
📋코드
# 14888 연산자 끼워넣기
import sys
from collections import deque
num = int(input())
a = list(map(int, sys.stdin.readline().split()))
# 덧셈, 뺄셈, 곱셈, 나눗셈 순서
operate = list(map(int, sys.stdin.readline().split()))
min_result = int(1e9)
max_result = int(-1e9)
# start : 다음 연산할 숫자 순서
# n : 지금까지 연산한 결과
# op : 남은 연산자 개수 배열
def bfs():
# start, n, op 순서대로 큐 삽입
queue = deque([[1, a[0], operate]])
while queue:
start, n, op = queue.popleft()
# 연산이 끝났을 때
if op.count(0) == 4:
global min_result, max_result
# 최솟값과 최댓값 갱신
min_result = min(min_result, n)
max_result = max(max_result, n)
continue
# 모든 연산자에 대해
for i in range(4):
# 연산자 개수를 다 썼으면 건너뜀
if op[i] <= 0:
continue
if i == 0: # 덧셈
tmp = [op[0] - 1, op[1], op[2], op[3]]
queue.append([start + 1, n + a[start], tmp])
elif i == 1: # 뺄셈
tmp = [op[0], op[1] - 1, op[2], op[3]]
queue.append([start + 1, n - a[start], tmp])
elif i == 2: # 곱셈
tmp = [op[0], op[1], op[2] - 1, op[3]]
queue.append([start + 1, n * a[start], tmp])
else: # 나눗셈
res = n // a[start]
# 음수를 양수로 나눌 때
# 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼다. (문제 조건)
if n < 0:
res = -n // a[start]
res = -res
tmp = [op[0], op[1], op[2], op[3] - 1]
queue.append([start + 1, res, tmp])
bfs()
print(max_result)
print(min_result)
