1976. 여행 가자

문제 링크

1976. 여행 가자

문제 코드

city = int(input())

goal_city = int(input())

city_graph =[[0 for i in range(city+1)]for j in range(city+1)]
visited = [0]*(city+1)
for i in range(1,city+1):
    num_list = list(map(int,input().split()))

    for j in range(1,city+1):
        city_graph[i][j] = num_list[j-1]

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

first_start = goal_city_list[0]

can_go_list=[first_start]
tmp_list = [first_start]
visited[first_start] = 1

while len(tmp_list) > 0:
    tmp = tmp_list.pop()

    for i in range(1,city+1):
        if city_graph[tmp][i] == 1 and visited[i] == 0:
            visited[i] = 1
            can_go_list.append(i)
            tmp_list.append(i)

result = "YES"

for goal in goal_city_list:
    if goal not in can_go_list:
        result = "NO"

print(result)

문제풀이

• 해당 문제에서는 가고자하는 노드가 연결만 되어 있으면 ok
• 따라서 가고자하는 노드 하나를 우선 등록하고, 해당 노드에 연결되있는 모든 노드를 can_go_list에 추가한다.
• tmp_list를 만들어서 연결돼있는 모든 노드를 찾도록 한다.
• can_go_list에 모든 goal_city가 있으면 yes출력