백준 1238 파티 파이썬 풀이, 반례

난이도 : 골드3

풀이일 : 05092

https://www.acmicpc.net/problem/1238

1238번: 파티

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

1차 시도 오답 -> 시간초과

import sys
from collections import deque

N, M, X = map(int, sys.stdin.readline().split())
load = deque([] for _ in range(N+1))
for _ in range(M):
    a, b, t = map(int, sys.stdin.readline().split())
    load[a-1].append([b-1, t])

maxi = 0

def shift(x, y):
    time = 0
    queue = deque([x])
    visited = [10000000] * M
    visited[x] = 1
    while queue:
        i = queue.popleft()
        if i == y:
            time = visited[i]
        for j in load[i]:
            if visited[i] + j[1] <= visited[j[0]]:
                visited[j[0]] = visited[i] + j[1]
                queue.append(j[0])
    return time - 1

for k in range(N+1):
    total = shift(k, X-1) + shift(X-1, k)
    if total > maxi:
        maxi = total

print(maxi)

코드 구성

• 메모리 절약을 위해 2차원 배열 대신 리스트에 도로, 시간 정보 저장
• shift 함수로 이동 가능한 세 곳에 대한 탐색
  • visited로 시간 저장
  • 최초 시간 1초로 시작하므로 time - 1 반환
• 가는 시간 + 오는 시간이 가장 긴 학생의 이동시간 출력

틀린 이유

• 가능한 모든 곳에 대한 탐색으로 시간초과 발생

---

2차 시도 오답

import sys
from collections import deque

N, M, X = map(int, sys.stdin.readline().split())
load = deque([] for _ in range(N))
for _ in range(M):
    a, b, t = map(int, sys.stdin.readline().split())
    load[a-1].append([b-1, t])

maxi = 0

def shift(x, y):
    time = 0
    queue = deque([x])
    visited = [10000000] * M
    visited[x] = 1
    while queue:
        i = queue.popleft()
        if i == y:
            time = visited[i]
            return time - 1
        for j in load[i]:
            if visited[i] + j[1] <= visited[j[0]]:
                visited[j[0]] = visited[i] + j[1]
                queue.append(j[0])

for k in range(N):
    total = shift(k, X-1) + shift(X-1, k)
    if total > maxi:
        maxi = total

print(maxi)

코드 변화

• y좌표를 찾았다면, 더 이상 조사하지 않고 return

틀린 이유

• y좌표 도달 시 바로 출력하도록 하여, 더 시간이 적게 드는 경우에도 재방문 불가능

---

최종 정답

import sys
from collections import deque

N, M, X = map(int, sys.stdin.readline().split())
load = deque([] for _ in range(N))
for _ in range(M):
    a, b, t = map(int, sys.stdin.readline().split())
    load[a-1].append([b-1, t])
maxi = 0    # 최대 이동시간

def shift(x, y):    # 이동함수 
    time = 10000000
    queue = deque([x])
    visited = [10000000] * M
    visited[x] = 1
    while queue:
        i = queue.popleft()
        if i == y and visited[i] < time:
            time = visited[i]    # 최소 이동시간 재할당
        if visited[i] > time:    # 유망성 조사
            continue
        for j in load[i]:    # visited 비교로 진입 조건 설정
            if visited[i] + j[1] <= visited[j[0]]:
                visited[j[0]] = visited[i] + j[1]
                queue.append(j[0])
    return time - 1    # 최초 1에서 시작

for k in range(N):    # 각 학생들의 이동시간 확인, 최대값 재할당
    time = shift(k, X-1) + shift(X-1, k)
    if time > maxi:
        maxi = time

print(maxi)

코드 변화

• i == y 일 때, 시간 비교 후 최소값 저장
• 시간 초과 방지를 위해 visited[i]가 time 초과 시 조사 중단

---

반례

입력	5 8 1 1 2 1 2 3 3 2 5 7 3 2 5 4 1 6 4 2 8 5 1 1 5 4 4
출력	18

---

느낀점

충분히 생각해서 한 번에 고칠 수 있는 조건이었는데 빨리 제출하고 싶은 마음에 한 번 더 틀렸다.

맨 처음에 오고 가는 길이 다를 수도있다는 조건을 빠트려서도 어이없게 한 번 더 틀렸고.

문제 제대로 읽고 로직 생각하고 접근하자