4/11 Coding Test

강의 듣고 과제하고 이해하고 구현하고 학교도 가고 하루가 순삭인 요즘..

코테 준비는 그래도 하루에 한 문제 씩이라도 틈틈이 하려 한다.✈️

✅ 문제 풀이 - BOJ (그래프 탐색)

🎈 1976 여행가자

도시 n개가 있고,임의의 두 도시 사이에 길이 있을 수도 있고 없을 수도 있다.
여행 일정이 주어질 때 가능한 경로인지 확인하는 문제
입출력은 다음과 같다.

• 입력: 첫 줄에 도시 수 n, 둘째 줄에 여행 계획에 속한 도시 수 m, 다음 n개 줄에는 n개의 정수가 주어지고 i번째 줄의 j번째 수는 i번 도시와 j번 도시 간의 연결 관계를 의미한다. (1은 연결, 0은 연결 X), 마지막 줄에 여행 계획이 주어진다.
• 출력: 경로가 가능하면 YES, 아니면 NO를 출력

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
route = list(map(int, input().split()))
parent = [i for i in range(n+1)]

def find(x):
    if parent[x] != x:
        return find(parent[x])
    return x
def union(a, b):
    a = find(a)
    b = find(b)
    if a > b:
        parent[a] = b
    else:
        parent[b] = a

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

start = find(route[0])
check = True
for i in route:
    if start != find(i):
        check = False
        break
if check:
    print('YES')
else:
    print('NO')

< 풀이 과정 >
union-find 알고리즘을 활용한 풀이.
간단하다고 생각했는데, 마지막 경로를 이용하여 한 집합에 속하는지 여부를 판단하는 것에 있어 시간이 좀 소요되었다. (12번 정도 틀린듯..)
구현 방식은 다음과 같다.

• find, union 함수 생성
• 2중 for문으로 graph[i][j]가 1이면 i, j는 인덱스이므로 union(i+1, j+1)로 같은 집합 처리
• 현 경로 초기값의 루트를 start로 지정하고 check로 확인해주는데, for문으로 route를 돌며 같은 집합이 아니면 check를 False처리 후 break 중단
• 이후 check를 이용하여 YES or NO로 출력한다.