문제
남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 잇는 도로들을 새로 만들거나, 안전상의 문제로 도로를 없애기도 할 계획이다. 도로 정비 계획은 두 도시와, 만들건지, 없앨건지에 대한 정보가 주어지는데, 도로를 정비하는 일은 매우 큰 일이기에 계획을 순서대로 하나씩 시행해 나갈 것이다. 상황에 따라서는 계획에 포함돼서 만들어진 도로를 제거할 수도 있다.
Zych는 차후 도로 정비 계획에 참고하기 위하여, 각 도시들이 수도에 방문하는데 최소 몇 개의 도시들을 방문해야 하는지 조사하기로 하였다.
남규나라의 초기 도시상태가 주어지고 도로 정비계획이 주어질 때, 한 도로가 정비될 때마다 각 도시별로 수도를 방문하는 데 최소 방문 도시들을 출력하시오.
입력
첫째 줄에는 도시의 개수 n,도로의 개수 m이 주어진다. 다음 m개의 줄에는 두 도시가 주어진다.(2≤n≤500,1≤m≤n*(n-1)/2)
다음 줄에는 도로 정비 계획에 들어가 있는 도로의 수 q가 주어지고, 다음 q줄에는 a i j가 주어지는데, a가 1일때는 두 도시 i,j를 잇는 도로를 만들고, a가 2일때는 i,j를 잇는 도로를 없앤다. (1≤q≤500,1≤a≤2, 1≤i,j≤n)
두 도시 사이에 이미 도로가 있는데 또 도로를 만들거나, 도로가 없는데 없애는 불가능한 경우는 입력으로 들어오지 않는다.
수도는 1번도시이다.
출력
q줄에 각 도시별로 수도를 방문하는 데 최소 방문 도시들을 출력하시오. 만약 수도를 방문하지 못한다면 -1을 출력하시오.
boj 14217
문제 설명
- 초기 도시 상태가 주어지고
- 도로가 계획에 따라 생기거나 없어진다.
- 도로가 갱신될 때 마다 수도(1번도시)로 가는 최소 거리를 출력하라.
풀이 과정
우선 각 도시에서 수도로 가는 최소 거리를 저장한 후, 갱신 될때마다 해당 도시만 확인하면 될 거라 생각했다.
#0 : 초기상태 [0, 1, 1, 2, 2]
#1 : 1과 2를 끊음 [0, 3, 1, 3, 2]
첫 계획에서 1과 2사이의 길이 끊겨 4번 도시의 경로는 "1-2-4" 가 아닌 "1-3-5-4"로 변화 되었다.
1과 2에서부터 bfs를 실행해 갱신이 멈출때까지 반복한다면 이 변화가 적용될 것이라 생각했다.
첫번째 코드
import sys
from collections import deque
input = sys.stdin.readline
def solve():
# n : 도시의 개수
# m : 도로의 개수
n,m = map(int,input().split())
# 초기 도시 상태
cities = [tuple(map(int,input().split())) for _ in range(m)]
# 앞의로의 계획
queue = [tuple(map(int,input().split())) for _ in range(int(input()))]
# 길 초기화
roads = [set() for _ in range(n)]
for a,b in cities:
roads[a-1].add(b-1)
roads[b-1].add(a-1)
# 최소 거리 초기화
visit = [False for _ in range(n)]
distances = [0 for _ in range(n)]
q = deque([0])
visit[0] = True
while q:
e = q.popleft()
for nxt in roads[e]:
if visit[nxt]:
continue
visit[nxt] = True
q.append(nxt)
distances[nxt] = distances[e] + 1
# 도로 갱신 함수
def refresh(cmd, city):
visit = [False for _ in range(n)]
visit[0] = True
# 거리 변화가 없는 경우
if any(distances[e] == distances[city] - 1 for e in roads[city]):
return
"""
"현재도시의 거리 +1"이 "다음도시의 거리" 과
1. 생성일 시 같거나 작다면
2. 파괴일 시 크다면
해당 경로로는 더이상 진행하지 않는다.
"""
q = deque()
q.append(city)
while q:
e = q.popleft()
for nxt in roads[e]:
if visit[nxt] or distances == -1 or\
(cmd == 1 and distances[e]+1 >= distances[nxt]) or \
(cmd == 2 and distances[e]+1 < distances[nxt]):
visit[nxt] = True
continue
visit[nxt] = True
q.append(nxt)
distances[nxt] = distances[e] + 1
# 도로 계힉 시작
for cmd,a,b in queue:
a -= 1
b -= 1
if cmd == 1:
roads[a].add(b)
roads[b].add(a)
elif cmd == 2:
roads[a].remove(b)
roads[b].remove(a)
refresh(cmd, a)
refresh(cmd, b)
print(*distances)
pass
if __name__ == "__main__":
solve()
여기에 예제 입력을 넣어보니 "2 2 4"부분에서 오류가 생겼다
#2 1과 4 사이의 도로가 생겼다. [0 2 1 1 2]
#3 2와 4 사이의 도로를 없앴다. [0 4 4 4 3] -> [0 3 1 1 2]
딱봐도 중간 cmd와 거리를 동시에 확인하는 코드에서 문제가 생긴듯 했다.
도로를 새로 생성할 때에는 문제가 없는거 같아 없앨 때의 알고리즘을 수정하다가 혹시 갱신할때 마다 bfs를 돌아도 되지 않을까 싶어 해봤는데 풀렸다.
최종 코드
import sys
from collections import deque
input = sys.stdin.readline
def solve():
# n : 도시의 개수
# m : 도로의 개수
n, m = map(int, input().split())
# 초기 도시 상태
cities = [tuple(map(int, input().split())) for _ in range(m)]
# 앞의로의 계획
queue = [tuple(map(int, input().split())) for _ in range(int(input()))]
# 길 초기화
roads = [set() for _ in range(n)]
for a, b in cities:
roads[a - 1].add(b - 1)
roads[b - 1].add(a - 1)
# 최소 거리 초기화
def bfs(visit,distances):
q = deque([0])
visit[0] = True
while q:
e = q.popleft()
for nxt in roads[e]:
if visit[nxt]:
continue
visit[nxt] = True
q.append(nxt)
distances[nxt] = distances[e] + 1
visit = [False for _ in range(n)]
distances = [0 for _ in range(n)]
bfs(visit,distances)
# 도로 계힉 시작
for cmd, a, b in queue:
a -= 1
b -= 1
if cmd == 1:
roads[a].add(b)
roads[b].add(a)
elif cmd == 2:
roads[a].remove(b)
roads[b].remove(a)
visit = [False for _ in range(n)]
bfs(visit, distances)
for i in range(n):
if not visit[i]:
distances[i] = -1
print(*distances)
pass
if __name__ == "__main__":
solve()그냥 처음부터 이렇게 했으면 30분만에 푼 거였는데, 괜히 최적화한답시고 다 돌지 않는 방법을 찾으려다가 3시간이 더 걸려버렸다. 다음부터는 문제가 요구하는 시간복잡도가 어느정도인지를 어림하고 시작해야 될 듯하다.
추가적으로 이제 매번 bfs를 실행하게 되었으므로 처음 한번의 bfs는 생략해도 되지만, 제출한 코드로 올려놓았다.
이후 과정
#3 2와 4 사이의 도로를 없앴다. [0 3 1 1 2]
#4 2와 5 사이의 도로를 없앴다 [0 -1 1 1 2]
#5 1과 2 사이에 도로를 놓았다. [0 1 1 1 2]
