1. 무슨 문제지?
문제 자체는 매우 심플하다고 볼 수도 있다. 요새 2호선으로 이사왔는데. 마음의 고향인 혜화 가고 싶다. 2호선 사람 너무 많아
2호선을 이용해보면 알겠지만 위는 순환선(빙 돌면 자기자리로 돌아오는)과 지선(도림천 ~ 까치산 or 용답 ~ 신설동)으로 이루어져 있다.
2호선이 인풋인줄 알았는데 그건 아니고, 3~3000개의 정점이 주어진다. 정점은 각각 1번부터 N번이라고 보면 되겠다.
문제는 각각의 정점이 순환선으로부터 얼마나 떨어져 있는지의 최솟값을 묻는 것이다. 거리는 정점간의 간선으로 한다. 가중치는 따로 없다. 즉, 양천구는 신도림~도림, 도림~양천구청이니까 2겠지?
2. 어떻게 풀었지?
전에 풀었던 Two dots처럼 일단 사이클을 구해야겠다고 생각했다. 사이클은 dfs로 풀면 될 것 같다고 생각했고, 여기까지는 괜찮았는데 뭔가 너무 비효율적일것 같다는 생각이 계속 들었다. 그래서 이래저래 인접행렬같은걸로 풀 수 있지 않을까 고민하다가 안되더라.
일단 인접리스트로 인풋을 받았다.
크게 두 가지 파트로 나뉜다.
- dfs로 순환선 찾기
- bfs로 거리 구하기
2-1. dfs
for문으로 각 정점을 다 돌면서 이게 순환선인지 아닌지를 is_cycle[i]에다 기록을 해 두었다. 이게 시간이 좀 오래 걸리지 않을까 싶었는데 다른 방법은 안떠올랐다.
dfs에서 사이클을 이루려면 최소 3개 이상의 정거장이 필요하기 때문에, count를 파라미터로 넘겨주었다.
안에 내용은 뭐 인접리스트 돌면서 dfs하고 true를 반환하면 결과적으로 true를 반환한다. true반환 조건은 count가 3 이상이면서 시작점(start)와 현재 도달한 지점(current)가 같은 곳이어야 하는 것.
여기서 약간 포인트는 dfs에서 쓰는 visited를 확인하기 전에, 위의 true 반환 조건을 먼저 넣어줘야 하는 것 같았다. 그래야 한바퀴 돌아서 원래 지점에 도착한 재귀가 시작할 때 바로 안 끝내고 확인하고 true를 반환하기 때문. 이 부분이 중요하지 않았나 싶다.
bfs는 아래로..
3. 어디서 해맸지?
dfs는 금방 짰는데 bfs에서 좀 해맸다. 계속 is_cycle에 들어가 있는 정점은 0으로 하고 나머지 지선의 정점들만 가지고 어떻게 해볼라고 생각하다 보니까... 재귀로 돌려서 최솟값 찾을까 싶기도 했는데 좀 비효율적일것 같았다.
그래서 bfs로 탐색을 해볼까 싶었는데 막상 어케 할 지 잘 생각이 안나더라..
dayliyhyun님 velog <- 너무 잘 정리해 주신 bfs 부분을 참고했다.
deque을 써서 구현하니까 수월한 것 같았다. 순환선의 정점들을 큐에다가 싹 넣어놓고, bfs 돌리면서 1씩 쌓아나가는거.. 많이 배운 것 같다.
그리고 이 문제를 python으로 풀면 어김없이 만나는 컴파일에러....
sys.setrecursionlimit()으로 해결하자
4. Code
import sys
from collections import deque
sys.setrecursionlimit(10**9)
def main() :
def dfs(start,count,current,visited,subway):
if count >=3 and start == current :
return True
if(visited[current]) :
return
visited[current] = True
for point in subway[current] :
if(dfs(start,count+1,point,visited,subway)) :
return True
return False
def bfs(is_cycle,distance,subway) :
q= deque()
for i in range(1,len(is_cycle)) :
if is_cycle[i] == True :
q.append(i)
while q :
front = q.popleft()
for next in subway[front] :
if is_cycle[next] == False :
is_cycle[next] = True
q.append(next)
distance[next] = distance[front]+1
for s in range(1,len(distance)) :
print(distance[s], end=" ")
N = int(sys.stdin.readline())
subway = [[] for _ in range(N+1)]
is_cycle = [False for _ in range( N+1)]
distance = [0 for _ in range(N+1)]
for i in range(N) :
x,y = map(int,sys.stdin.readline().split())
subway[x].append(y)
subway[y].append(x)
for i in range(1,N+1) :
visited = [False for _ in range(N+1)]
check_cycle = dfs(i,0,i,visited,subway)
is_cycle[i] = check_cycle
bfs(is_cycle,distance,subway)
if __name__ == "__main__" :
sys.exit(main())사실 main 함수 선언하고 안에다가 코딩하는거 해보고 싶었다 ㅎㅎ
java 언제하지;
