[Python] 백준 1976번 - 여행 가자

문제

• 백준 1976번

최종 코드

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
m = int(input())
cities = [[0] for _ in range(n + 1)]


# 연결 여부 확인
def check_path(start, end):
    if start == end:
        return True

    que = deque()
    que.append(start)
    visited = [False] * (n + 1)
    visited[start] = True

    while que:
        now = que.popleft()
        if cities[now][end] == 1:
            return True

        for i in range(1, len(cities[now])):
                if cities[now][i] == 1 and not visited[i]:
                    visited[i] = True
                    que.append(i)

    return False


for i in range(1, n + 1):
    line = list(map(int, input().split()))
    cities[i] += line

routes = list(map(int, input().split()))

possible = True

for i in range(len(routes) - 1):
    possible = check_path(routes[i], routes[i + 1])

    if not possible:
        break

if possible:
    print("YES")
else:
    print("NO")

풀이 과정

---

• 문제의 입력으로는 도시의 수 N과 여행 계획에 속한 도시의 수 M이 주어진다
  • 사실 아직까지 M이 왜 주어지는지는 모르겠...
• 이후 N개의 줄에는 도시의 연결 정보가 인접 행렬의 형태로 주어지며 방향성은 없는 그래프이다
• 그래프 탐색을 이용(BFS) 하여 여행 계획에서 반복을 통해 앞날의 도시와 뒷날의 도시가 연결되어 있는지 확인하여 여행 가능 여부를 판별하자라는 생각이 들었다!

 

초기 코드

<hide/>
import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
m = int(input())
cities = [[0] for _ in range(n + 1)]


def check_path(start, end):
    que = deque()
    que.append(start)
    visited = [False] * (n + 1)
    visited[start] = True

    while que:
        now = que.popleft()

        if cities[start][end] == 1:
            return True
        
        for i in range(1, len(cities[now])):
                if cities[now][i] == 1 and not visited[i]:
                    visited[i] = True
                    que.append(i)
    
    return False


for i in range(1, n + 1):
    line = list(map(int, input().split()))
    cities[i] += line

routes = list(map(int, input().split()))

possible = True

for i in range(n - 1):
    possible = check_path(routes[i], routes[i + 1])

    if not possible:
        break
        
if possible:
    print("YES")
else:
    print("NO")

 

 

문제점

---

        1. check_path 함수 내(19번째 줄) 도시 연결 여부 조건이 잘못 설정되었다

# start(앞날), end(뒷날)만 연결되어 있는지 확인 -> (A-B-C)로 이어진 경우 (A-C) 확인 불가
if cities[start][end] == 1:
	return True
    
# 아래와 같이 수정; now -> start와 연결되어 있는 도시 중 현재 큐에서 꺼낸 도시(노드)
if cities[now][end] == 1:
	return True

       

        2. 38번째 줄 routes list의 범위가 잘못 설정되었다

 

# routes list의 길이는 n과 관련이 없다...
for i in range(n - 1):
    possible = check_path(routes[i], routes[i + 1])
    
# len() 함수 이용하여 수정
for i in range(len(routes) - 1):
    possible = check_path(routes[i], routes[i + 1])​

 

        3. 여행 경로가 A-A와 같이 같은 도시가 연달아 나올 경우 NO가 출력된다

                위의 두 가지 문제점을 고쳐도 계속 오답으로 나와 이유를 고민하는 중 해당 반례를 찾게 되었다

                [반례]

# check_path 함수 실행 초기에 두 매개변수를 비교하는 조건식을 추가!
if start == end:
	return True

 

• 문제에서 주어진 인접 행렬 형태의 데이터를 그대로 저장하지 않고 인접 리스트 형태로 변환했다면 조금 더 빠르지 않을까 아쉬움이 있었다
• 사용했던 반례

// 전날과 다음날의 일정이 같은 경우
3
2
0 1 0
1 0 1
0 1 0
1 1

answer => YES

 

틀린 부분 또는 궁금한 점은 댓글로 남겨주세요! 항상 환영합니다!