문제
한국에 처음 도착한 미국인 Mr.Goofcode는 한국의 수도 서울을 여행할 생각에 들떠 있었다. 하지만, 공항 철도를 타고 서울역에 도착한 Mr.Goofcode는 복잡한 서울의 지하철 노선도를 보고 경악을 금치 못했다. 왜냐하면, 서울역을 포함한 서울의 모든 역은 이름이 아닌 숫자로 구분해야 했으며, 운영되는 지하철의 종류(호선)가 너무 많아 최적의 이동 경로를 계산하기 어려웠기 때문이다.
Mr.Goofcode는 패닉에 빠져 평소 메일로 편지를 주고 받던 당신에게 도움을 요청했다. 평소 Mr.Goofcode에게 도움을 받았던 당신은 그를 위해 지하철 노선도 어플리케이션을 만들어 주려고 한다. 그러나, 까다로운 Mr.Goofcode는 걷는 것을 매우 싫어한다. 따라서, 그를 위해 가능하면 어플리케이션이 제시하는 지하철 환승 횟수를 최소로 줄이고 싶어 한다.
Mr.Goofcode를 위해 주어진 지하철 노선도를 보고 Mr.Goofcode가 목적지에 도달하기 위해 최소 몇 번의 환승이 필요한지 구해주자. 단, Mr.Goofcode의 출발역인 서울역의 역 번호는 항상 0번이다.
지하철의 '호선'이란 한 종류의 지하철에서, 다른 지하철로 환승하지 않고 이동할 수 있는 역의 집합을 의미한다. 지하철의 '역'이란 지하철의 호선의 원소로 지하철이 방문할 수 있는 정점을 의미한다. 각 역은 간선으로 연결 관계를 나타낼 수 있으며, 이 간선을 통해서만 지하철이 이동할 수 있다. 지하철은 양 방향으로 이동할 수 있다.
입력
첫째 줄에 서울의 지하철 호선의 개수 N(1 ≤ N ≤ 10)이 주어진다.
둘째 줄부터, 순서대로 1호선부터 N호선까지, 각 호선의 역 개수 K(1 ≤ K ≤ 10)와 각 지하철 호선이 포함하는 역의 번호aN1, aN2, aN3, ... aNK가 한 줄에 주어진다. 각 역의 번호는 모두 다르며 0이상 232-1 이하의 정수임이 보장되어 있다.
입력의 마지막 줄에는, 도착역의 번호가 주어진다.
각 지하철 호선 중, 순환선이 있을 수 있음에 주의하자, 순환선의 입력은 호선이 포함하는 역의 번호가 a1, a2, a3, ... aK-1, a1 의 꼴로 주어진다. (예제 2번)
출력
출발 역(서울 역)에서 도착 역까지 최소 환승 횟수를 한 줄에 출력한다. 단, 도달할 수 없는 경우 -1을 출력한다.
예제
알고리즘 1
n개월 전, 처음 접했을 때 부터 감을 못잡아서 미루고 미루고 까먹었다가 이제야 해결하게 된 지옥의 지하철........... 16166...... 가만 안 둬
이번에도 이틀을 넘게 고민했지만 도저히 모르겠어서 다른 분의 코드를 공부하기로 했다.
선생님 아니였으면 절대 해결 못했을 듯.. 눈물 광광 애증의 16166
1. 자료구조
딕셔너리 + 리스트
-
h: {역 번호 : 역이 포함된 노선 정보(리스트)}- 해당 역이 몇 개의 노선을 가지는지 쉽게 알 수 있음
bfs함수에서 두 개 이상의 노선을 가지는 역은 따로 저장
-> 새로운 노선으로 다시bfs를 진행할 때 환승 횟수 저장 용이
-
route: {역 번호: 역이 포함된 노선의 모든 역 번호(리스트)}- 인접한 역 정보만 저장하는 것보다 간편함
2. BFS
- 기존
bfs방식으로 탐색을 하면 환승 여부를 알기 힘듦
-> 환승 여부와 빈도수를 알 수 있도록 변형 필요
def bfs(start, dest, cnt):
#방문할 역 리스트(환승역이 저장됨)
havetogo = []
#start역과 같은 노선에 있는 모든 역 번호 탐색
for x in route[start]:
#만약 도착점을 찾으면 cnt(환승 횟수) 반환
if x == dest:
return cnt
#만약 x역의 노선이 한 개 이면서 방문하지 않은 역이라면 x역을 방문 처리
if len(h[x]) == 1 and x not in vis:
vis.append(x)
#x역의 노선이 두 개 이상이면서(환승 가능역) 방문하지 않은 역이라면 x역 방문 처리, 다시 방문할 리스트에 저장
else:
if x not in vis:
vis.append(x)
havetogo.append(x)
#다시 방문할 리스트에 있는 역 bfs, 환승횟수(cnt) 증가
for x in havetogo:
return bfs(x, dest, cnt + 1)알고리즘 2
위 코드를 분석하고 공부하면서 기존에 내가 집착하던 것과 답답하게 했던 자료형 등을 모두 버렸다. 그리고 새 코드를 작성하는데 아무래도 정답을 알고난 후 완전히 새로운 방식의 코드를 작성하는 건 어려웠다.
참고만 하고 내 코드를 짜고 싶었는데 ㅠㅠ 불가...
코드를 똑같이 치는 건 양심에 찔리고 공부도 안 될 것 같아서 이리저리 고민하다가 위 코드를 조금 진짜 쪼오오오오오오끔 보완(도 아님 사실)하는 방식으로 코딩을 해봤다! 근데 결국 거의 똑같음
1. 자료구조
딕셔너리 + 리스트 -> 그대로 사용
-
h->station그대로 사용 -
route->line노선 정보를 좀 더 쉽게 저장하고, 최대한 중복이 없게 저장하고 싶었다.
노선 정보 자체에 접근해서 해결할 수 있기 때문에!오히려 복잡할 수 있다는 게 함정
2. BFS
- 데이터가 변경되었기 때문에 데이터에 접근하는 것만 변경됨
->start역과 같은 노선에 있는 모든 역 정보를 미리 저장해놓지 않고,line에 접근하게 함
ex)10번역
############ 알고리즘 1
#10번 역의 노선 = 2, 3호선
h[10] = [2, 3]
#10번 역이 포함된 노선의 모든 역 번호 = 2, 5, 7, 10, 10, 8
route[10] = [2, 5, 7, 10, 10, 8]
############ 알고리즘 2
#10번 역의 노선 = 2, 3호선
station[10] = [2, 3]
#2호선의 역 = 2, 5, 7, 10
line[2] = [2, 5, 7, 10]
#3호선의 역 = 10, 8
line[3] = [10, 8]- 중복되는 코드라인을 없애기 위해서 조건문을 적절하게 변경
- 사실 작동이 거의 비슷함
def bfs(start, cnt):
#방문할 역 리스트(환승역이 저장됨)
togo = []
#l: start역의 노선 정보(몇 호선)
for l in station[start]:
#l호선의 모든 역을 탐색
for y in line[l]:
#만약 도착점을 찾으면 cnt(환승 횟수) 반환
if y == dest:
return cnt
#만약 y역이 방문하지 않은 역이라면 y역 방문 처리
if y not in visited:
#만약 y역의 노선이 1개 초과라면 다시 방문할 리스트에 저장
if len(station[y]) > 1:
togo.append(y)
visited.append(y)
#다시 방문할 리스트에 있는 역 bfs, 환승횟수(cnt) 증가
for x in togo:
return bfs(x, cnt + 1)코드
from sys import stdin
def bfs(start, cnt):
togo = []
for l in station[start]:
for y in line[l]:
if y == dest:
return cnt
if y not in visited:
if len(station[y]) > 1:
togo.append(y)
visited.append(y)
for x in togo:
return bfs(x, cnt + 1)
n = int(stdin.readline().strip())
visited = []
line = {}
station = {}
for line_num in range(1, n + 1):
tmp = list(map(int, stdin.readline().split()))
line[line_num] = tmp[1:]
for a in tmp[1:]:
if a in station:
station[a].append(line_num)
else:
station[a] = [line_num]
dest = int(stdin.readline().strip())
visited.append(0)
cnt = bfs(0, 0)
if cnt == None:
print(-1)
else:
print(cnt)
