글 읽기 - 서울의 지하철 질문 있습니다.

hello70825 5년 전 1

입력 호선에 각 지하철 호선 중, 순환선이 있을 수 있음에 주의하자, 순환선의 입력은 호선이 포함하는 역의 번호가 a₁, a₂, a₃, ... a_K-1, a₁ 의 꼴로 주어진다. (예제 2번) 라고 적혀있어서, 만약 순환선이라면 K리스트에 a₁, a₂, a₃, ... a_K-1로 저장하기 위해서 9번째 줄을 추가하였는데 이 부분을 추가할 경우 틀렸다고 나옵니다.

b[0]은 b리스트의 첫 번째 값

b[-1]은 b리스트의 마지막 값

b = b[:len(b)-1:] 는 b리스트에서 마지막 값을 제외하고 다시 리스트를 만드는 것

아닌가요?

왜 틀렸다고 나오는지 모르겠습니다.

n = int(input())
K = [[] for _ in range(n + 1)]
S = [[] for _ in range(n + 1)]
D = [float('inf')] * (n + 1)

# 값을 입력받고, 몇 호선에 무슨 역이 있는지 볼 수 있는 리스트K 에 저장해둠
for i in range(1, n + 1):
    a, *b = map(int, input().split())
    #if b[0] == b[-1]: b = b[:len(b) - 1:] 이 부분을 추가하면 틀렸다고 나옴
    for j in range(len(b)):
        K[i].append(b[j])
        
# 모든 호선을 탐색해서 환승 할 수 있는 역이 있는지 확인하고, 있다면 i호선에 x호선을 추가, x호선에 i호선을 추가
for i in range(1,n+1):
    for j in range(len(K[i])):
        for x in range(i+1,n+1):
            for y in range(len(K[x])):
                if K[i][j]==K[x][y]:
                    S[i].append(x)
                    S[x].append(i)

# 모든 호선을 탐색해서 0번역을 찾음. 그리고 0번역이 있는 호선을 deque에 넣어주고,
# 0번역은 환승할 필요가 없으므로 최소 환승 값을 구하는 리스트 D에 D[호선]=0 을 설정해줌
q=deque()
for i in range(1,n+1):
    for j in range(len(K[i])):
        if K[i][j]==0:
            D[i]=0
            q.append(i)
                    
#BFS
while q:
    x=q.popleft()
    for nx in S[x]:
        if D[nx]>D[x]+1:
            D[nx]=D[x]+1
            q.append(nx)
            
# 마지막 값을 입력받고, 도착 역이 있는 호선이 여러 곳일 수 있으니 가장 적은 환승의 수를 min을 이용해 ans에 저장해둠
k=int(input())
ans=float('inf')
for i in range(1,n+1):
    for j in range(len(K[i])):
        if K[i][j]==k:
            ans=min(ans,D[i])
            
#도착역을 방문할 수 없으면 -1 출력, 방문할 수 있으면 ans를 출력
print(-1 if ans==float('inf') else ans)

jh05013 5년 전 1

틀렸습니다가 아니라 런타임 에러가 나옵니다.

hello70825 5년 전 1

맨 윗 줄 deque를 안써놨네요ㅠ

from collections import deque
n = int(input())
K = [[] for _ in range(n + 1)]
S = [[] for _ in range(n + 1)]
D = [float('inf')] * (n + 1)
for i in range(1, n + 1):
    a, *b = map(int, input().split())
    # if b[0] == b[-1]: b = b[:len(b) - 1:] 이 부분을 추가하면 틀렸다고 나옴
    for j in range(len(b)):
        K[i].append(b[j])
for i in range(1, n + 1):
    for j in range(len(K[i])):
        for x in range(i + 1, n + 1):
            for y in range(len(K[x])):
                if K[i][j] == K[x][y]:
                    S[i].append(x)
                    S[x].append(i)
q = deque()
for i in range(1, n + 1):
    for j in range(len(K[i])):
        if K[i][j] == 0:
            D[i] = 0
            q.append(i)
while q:
    x = q.popleft()
    for nx in S[x]:
        if D[nx] > D[x] + 1:
            D[nx] = D[x] + 1
            q.append(nx)
k = int(input())
ans = float('inf')
for i in range(1, n + 1):
    for j in range(len(K[i])):
        if K[i][j] == k:
            ans = min(ans, D[i])
print(-1 if ans == float('inf') else ans)

jh05013 5년 전 2

1
1 0
0

hello70825 5년 전 1

호선에0번역하나거나0부터시작하는순환선을생각못했네요ㅠㅠ감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

서울의 지하철 질문 있습니다.

hello70825 5년 전 1

jh05013 5년 전 1

hello70825 5년 전 1

jh05013 5년 전 2

hello70825 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말