2644 - 촌수계산

www.acmicpc.net/problem/2644

2644번: 촌수계산

dfs, 인접리스트를 통해 쉽게 풀 수 있는데 촌수를 계속 저장을 시켜줘야함으로 list를 하나 더 만들어 함수에 촌수를 저장할 변수를 계속 넘겨주며 촌수관련 list에 넘겨줘야한다. 나는 어차피 check배열을 사용해야하기에, check배열에 촌수를 저장하였고 복잡함을 줄이기 위해 다른 list는 사용하지 않았다.

*tip

-1로 예외처리를 해줘야하기 때문에 코드를 돌리면서(for문을 돌리며) print하는 것이 아니라 for문이 끝나면 check배열을 따져서 원하는 숫자에 '0'이 들어있다면 -1을 출력, 숫자가 들어있다면 그대로 출력하는 형태로 이후에 한번에 처리.

---

n = int(input())
a,b = map(int,input().split())
m= int(input())

list_ = [[0]*(n+1) for _ in range(n+1)]
check = [0]*(n+1)

for i in range(0,m):
    x,y = map(int,input().split())
    list_[x][y] = 1
    list_[y][x] = 1


def dfs(temp,cnt):
    for i in range(1,n+1):
        if list_[temp][i]==1 and check[i]==0:
            check[i]=cnt
            if i==b:
                check[i]=cnt
                break
            dfs(i,cnt+1)
    return

for i in range(1,n+1):
    if list_[a][i]==1 and check[i]==0:
        if i==b:
           check[i]=1
           break
        check[i]=1
        dfs(i,2)


if check[b]==0:
    print("-1")
else:
    print(check[b])

---