[BAEKJOON/Python] no.2644 촌수계산 | DFS/BFS

문제

---

https://www.acmicpc.net/problem/2644

2644번: 촌수계산

 

 

1차 풀이

---

from collections import deque
people_count = int(input())
target1, target2 = map(int, input().split())
relationship_count = int(input())

graph = [[] for _ in range(people_count + 1)]
check = [0] * (people_count + 1)
for _ in range(relationship_count):
    parents, child = map(int, input().split())
    graph[parents].append(child)
    graph[child].append(parents)
    
def bfs(start):
    q = deque()
    q.append(start)
    
    while q:
        node = q.popleft()
        for n in graph[node]:
            print('now i am checking', n)
            if check[n] == 0:
                check[n] = check[node] + 1
                q.append(n) 

bfs(target1)

if check[target2] > 0:
    print(check[target2])
else:
    print(-1)

👉🏻bfs를 통해 풀었고 구글링을 참고해 내 전체 코드는 위와 같다ㅎㅎ 한 부분씩 살펴보장!

from collections import deque

people_count = int(input())
target1, target2 = map(int, input().split())
relationship_count = int(input())

graph = [[] for _ in range(people_count + 1)]
check = [0] * (people_count + 1)
for _ in range(relationship_count):
    parents, child = map(int, input().split())
    graph[parents].append(child)
    graph[child].append(parents)

👉🏻먼저 변수 선언 부분이다.

• bfs를 사용하기 위해 deque를 import했다.
• 전체 사람의 수를 people_count에, 관계를 구해야 하는 사람을 각각 target1과 target2에 할당하고 관계의 수를 relationship_count에 할당했다.
• for 문을 돌리며 graph를 완성시키고 촌수를 담을 check 리스트를 만들어 두었다.

# graph
# [[], [2, 3], [1, 7, 8, 9], [1], [5, 6], [4], [4], [2], [2], [2]]

# check
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

👉🏻graph와 check을 출력하면 위와 같다.

def bfs(start):
    q = deque()
    q.append(start)
    
    while q:
        node = q.popleft()
        for n in graph[node]:
            if check[n] == 0:
                check[n] = check[node] + 1
                q.append(n)

👉🏻bfs 함수는 다음과 같다.

• 탐색할 노드를 담을 데크 q를 선언하고 인자로 받은 start라는 노드를 넣는다.
• q가 빌 때까지 while문을 돌린다.
  • q의 첫 번째 요소를 꺼내 node로 선언한다.
  • graph에서 node와 연결된 또다른 n들을 for문에 돌리면서 탐색한다.
  • check에 담긴 숫자가 0이면 아직 탐색을 하지 않은 노드이므로 수를 갱신하고 q에 넣어준다. check[node] + 1로 갱신하는 이유는 n에 오기까지 node를 거쳐오기 때문이다. 

def bfs(start):
    q = deque()
    q.append(start)
    
    while q:
        node = q.popleft()
        print('-----')
        print('the node is ', node)
        for n in graph[node]:
            print('now i am checking', n)
            if check[n] == 0:
                check[n] = check[node] + 1
                print('and check is', check)
                q.append(n)

👉🏻다음과 같이 print문을 넣어서 출력하면 아래와 같이 나온다.

👉🏻로직을 이해하는 데에 도움이 되면 좋겠다!

bfs(target1)

if check[target2] > 0:
    print(check[target2])
else:
    print(-1)

👉🏻마지막으로 bfs에 target1을 넣어서 실행한다. 그리고 check리스트를 확인해 0보다 크면 해당 숫자를 그렇지 않으면 -1을 출력한다.