[백준] 1976번 : 여행 가자 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1976번: 여행 가자

 

1. 문제 설명

2. 풀이과정

해당 문제는 도시의 연결 유무를 유니온 파인드 연산을 이용해 해결할 수 있다.

유니온 파인드는 그래프 영역에서 많이 활용되지만, 해당 문제와 같이 단독으로도 활용할 수 있다.

문제에서는 도시 간 연결 데이터를 인접 행렬의 형태로 주기 때문에 인접 행렬을 탐색하면서 연결될 때마다 union 연산을 수행하는 방식으로 문제에 접근한다.

 

도시와 여행 경로 데이터를 저장하고 각 노드와 관련된 대표 노드를 저장한 리스트를 생성한다.

대표 노드를 저장한 리스트는 1차원으로 생성하며 처음에는 각 자신의 노드를 대표 노드로 저장한다.

도시 간 연결 정보는 2차원 리스트의 형태로 저장한다.

이때 도시의 번호는 1부터 시작되는 반면, 리스트의 인덱스는 0부터 시작하기 때문에 이를 고려하여 생성한다.

 

도시 연결 정보가 저장된 인접 행렬을 탐색하면서 도시가 연결되어 있을 때 union 연산을 수행한다.

항상 큰 도시가 대표가 되도록 union 연산의 매개변수를 변경한다.

여행 경로에 포함된 도시의 대표 노드가 모두 같은지 확인한 후 결과를 출력한다.

 

슈도코드

1. N(도시의 수) 입력받기
2. num(대표 노드를 저장할 리스트) 생성 및 초기화
3. M(여행 계획에 속한 도시의 수) 입력받기
4. city(도시 연결 데이터 리스트) 생성
5. for N만큼 반복: 도시 연결 데이터를 입력받아 city 리스트에 저장
6. (도시 번호가 1부터 시작이기 때문에 0번째 index에 0 데이터 추가)
7. plan(여행 계획 도시 저장 리스트)
8. union 연산 union(i, j):
   1. if (i와 j의 대표 노드가 다르면): 두 원소의 대표 노드끼리 연결
9. find 연산 find(i):
   1. if (i가 대표 노드이면): i 반환
   2. else:
      1. i의 대표 노드 값을 find(num[i]) 값으로 저장 (재귀 함수 형태)
      2. i의 대표 노드 값 반환
10. for i 1~N까지 반복:
    1. for j 1~N까지 반복:
       1. if (city[i][j] == 1): union(i, j) 연산 수행
11. check(연결 여부 저장 변수)
12. for 1 ~ plan 개수만큼 반복:
    1. if (여행 시작 도시의 대표 노드 != 여행 계획 도시들의 대표 노드):
       1. check = False (계획대로 여행이 불가능)
       2. break (판별 종료)
13. if (check): YES 출력
14. else: NO 출력

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())
num = [i for i in range(N + 1)]

M = int(sys.stdin.readline())

city = [[0] * (N + 1)]
for _ in range(N):
    city.append([0] + list(map(int, sys.stdin.readline().split())))

plan = list(map(int, sys.stdin.readline().split()))

def union(i, j):
    if (find(i) != find(j)):
        num[find(j)] = find(i)

def find(i):
    if (i == num[i]):
        return i
    else:
        num[i] = find(num[i])
        return num[i]

for i in range(1, N + 1):
    for j in range(1, N + 1):
        if (city[i][j] == 1):
            union(i, j)

check = True
for i in range(1, len(plan)):
    if (find(plan[0]) != find(plan[i])):
        check = False
        break

if (check):
    print('YES')
else:
    print('NO')