ABCDE

DFS로 풀지 BFS로 풀지 판단하기 쉽지 않았다. 기존의 문제들은 DFS인지 BFS인지 카테고리를 알고 풀었기에 바로 접근할 수 있었는데, 모르고 문제를 보니 생각보다 판단이 잘 서지 않았던 것 같다.

문제 분석

  • A는 B와 친구다.
  • B는 C와 친구다.
  • C는 D와 친구다.
  • D는 E와 친구다.

위와 같은 관계의 ABCDE가 존재하는지 알아내면 된다. 그래프에서 깊이가 5인 경우를 찾는 문제와 동일하다. 서로 다른 사람 ABCDE가 위와 같이 연결되어 있는지 찾아내면 되는 것이다.

먼저 입력을 통해 dictionary에 친구 관계를 입력했다. 이후, DFS를 이용해 깊이 탐색을 한다. 각각의 사람에 대해 깊이 탐색을 수행하고, 깊이가 5가 되는 지점이 있으면 1을 출력하고 시스템을 종료시켰다. 만약에 시스템이 종료되지 않고 for문이 종료된다면, 깊이가 5가 되는 지점이 없다는 뜻임으로 0을 출력한다.


시행착오

  • 깊이 check리스트를 만들어 친구를 방문하면 그자리를 1로 업데이트했다. 이후, check리스트의 합이 5가 되면 값이 1인 친구가 5명이 존재한다는 뜻임으로 1을 출력하고 시스템을 종료했었다. 하지만, 사람 수가 많아지면 시간 복잡도가 증가해 시간초과가 발생했고, cnt변수를 하나 더 만들어서 깊이를 탐색했다.

  • BFS DFS로 풀다가 시간초과가 발생하자 별 생각없이 BFS로 바꿔서 풀기 시작했다. 하지만, BFS로 풀면 최단거리가 나오기 때문에 원하는 결과를 얻지 못했다. 예를 들어서

8 8
1 7
3 7
4 7
3 4
4 6
3 5
0 4
2 7

input이 다음과 같을 때, 0으로 부터의 BFS를 시행하고, 최단거리(시작지점이 1이다.)를 저장한 리스트를 출력하면 아래와 같은 결과가 나온다.

[1, 4, 4, 3, 2, 4, 3, 3]

0>4>7>3>5 이렇게 ABCDE를 만족시키는 값이 존재하지만, 위의 결과에서는 5를 찾아볼 수 없다. 따라서, 만약에 BFS로 풀고 싶다면, 일반적인 BFS가 아니라 추가적인 코드를 따로 작성해 주어야 할 것이다.


CODE

import sys
read=sys.stdin.readline

n,m=map(int,read().split())

friends=dict()
for _ in range(m):
    a,b=map(int,read().split())
    if a in friends:
        friends[a].append(b)
    else: friends[a]=[b]
    if b in friends:
        friends[b].append(a)
    else: friends[b]=[a]

check=list(0 for _ in range(n))

cnt=0
#cnt를 사용하지 않고, check배열의 1의 개수로
#문제의 조건을 판단하면 시간초과가 발생했다.

def dfs(x):
    global cnt
    check[x]=1
    cnt+=1
    if cnt==5:#깊이가 5 >> ABCDE를 만족하는 친구들이 존재한다는 뜻이다.
        print(1)
        sys.exit()

    for i in friends[x]:
        if check[i]==0:
            dfs(i)
    cnt-=1
    check[x]=0

for i in range(n):
    dfs(i)
#종료되지 않고 여기까지 넘어오면 ABCDE를 만족하는 친구들이 존재하지 않는다는 뜻이다.
print(0)


CODE - BFS로 시도했던 코드

import sys
read=sys.stdin.readline

n,m=map(int,read().split())
friends=dict()
for _ in range(m):
    a,b=map(int,read().split())
    if a in friends:
        friends[a].append(b)
    else: friends[a]=[b]
    if b in friends:
        friends[b].append(a)
    else: friends[b]=[a]

from collections import deque

def bfs():
    for i in range(n):
        point=deque([i])
        check=list(0 for _ in range(n))
        check[i]=1
        while point:
            a=point.popleft()

            for j in friends[a]:
                if check[j]==0:
                    check[j]=1+check[a]
                    if check[j]==5:
                        print(1)
                        sys.exit()
                    point.append(j)
            #print(check)
bfs()
print(0)


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]