[Python Algorithm] Contact SWEA #1238

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

내 문제 풀이

from collections import deque

for t in range(10):
    l, s = map(int, input().split())
    lst = list(map(int, input().split()))
    maximum = max(lst)
    memory = [set() for _ in range(maximum)]

    for i in range(0, l, 2):
        memory[lst[i]-1].add(lst[i+1])
    for i in range(len(memory)):
        memory[i] = list(memory[i])

    visited = [0 for _ in range(maximum)]
    queue = deque()

    if len(memory[s-1]) == 0:
        print(s)
    else:
        for i in memory[s-1]:
            queue.append((i, 1))
        while queue:
            (n, cnt) = queue.popleft()

            if visited[n-1] > 0:
                continue

            visited[n-1] = cnt

            if len(memory[n-1]) == 0:
                continue

            for i in memory[n-1]:
                queue.append((i, cnt+1))

        maxResult = max(visited)
        answer = 0
        for i in range(maximum):
            if visited[i] == maxResult:
                answer = max(answer, i+1)
        print("#" + str(t+1) + " " + str(answer))

👉 BFS 문제

• lst 리스트에 주어지는 값을 입력받고, 그 중 최댓값을 구해서 그 범위만큼 memory 리스트를 생성했다.
• memory에는 한 사람이 어떤 숫자의 사람에게 연락을 보낼 수 있는지에 대한 정보를 가진다.
  ex) 1번 사람이 7, 8, 17번에게 연락을 보낼 수 있다고 하면 memory[0] = {7, 8, 17}
  같은 연락망이 여러 번 입력될 수 있다고 했으므로, 중복 제거를 위해 set 형태의 원소로 구성했다.
  그리고 모든 정보 입력이 끝나면 다시 그 set들을 리스트로 형변환해주었다.
• visited 리스트는 bool이 아닌 int형으로 만들어서 가장 마지막에 방문한 곳을 알 수 있도록 했다.
• queue에는 시작점에서 이어지는 점과, 몇 번째로 방문인지 표현하는 값을 튜플 쌍으로 넣어주었다.
  그리고 while 반복을 하며 queue의 가장 첫 번째 원소 값을 n, cnt에 할당해서 사용했다.
• visited[n-1]이 0보다 크다면 이미 연락을 받은 곳이므로 다시 연락할 수 없고, continue 했다.
  그렇지 않을 경우에는 visited[n-1]에 cnt를 저장해서 몇 번째로 방문하는 점인지를 표시했다.
• memory[n-1]에 저장된 값이 없다면 해당 점은 연락할 수 있는 곳이 없는 것이므로 continue 했다.
  그렇지 않을 경우에는 memory[n-1]에 저장된 점들을 모두 queue에 추가했다.
• queue가 빌 때까지 위의 과정을 반복하고, 반복이 끝나면
  visited에서 가장 큰 값을 가진 원소 중 가장 큰 수를 찾아서 결과로 출력했다.

 

💡 피드백

• 시작점을 기준으로 계속 탐색할 곳들을 적절히 찾아주면 되는 간단한 문제였다.