[백준/Python] 13023- ABCDE

13023- ABCDE

1. 문제 해석

쉽게 말해 5명이 이어져 있는 가를 판단하고, 이어져있다면 1 아니라며 0을 출력한다.

ex )(0-1), (1-2), (2-3), (3-4), (4-5) 으로 1-2-3-4-5가 연결된 것으로 1을 출력한다.

ex )언뜻 보면 (0-1), (1-2), (2-3), (3-0) 으로 0-1-2-3-0 으로 4개만 연결된 것처럼 보이는데, 4부터 시작하는 것을 생각했을 때 4-1-2-3-0 으로 5개가 연결되어 있다.

2. 문제 접근

연결 관계를 확인하고 방문 처리를 해야하는 문제라고 판단이 들었다.
다만, 5개의 연결 관계를 빠르게 파악하는 게 우선이기 때문에 BFS보단 DFS가 더 적합하다고 판단했다.

3. 알고리즘 풀이

A(depth=1)를 시작으로 (depth=5)까지 가게 된다면 5명이 연결된 것으로 간주한다.

1. 처음 start를 시작으로 연결 관계를 확인한다.
2. 종료 조건 : 트리의 깊이가 5가 된다면 멈추고, 1을 출력
3. for i in range(N) 을 통해 start를 바꿔가며 DFS를 실행

N,M = map(int,input().split())
arr=list([] for _ in range(N))
visited=[False] * N
for _ in range(M): # 간선 정보 입력
    a,b=map(int,input().split())
    arr[a].append(b)
    arr[b].append(a)
five = False # 5명 연결시 True

def dfs(start,depth):
    global five
    visited[start]=True

    if depth==5 : # 5명 연결확인
        five = True
        return
    for i in arr[start]: # 연결된 것들중에
        if visited[i] == False : #방문하지 않은게 있는지 확인
            dfs(i,depth+1)
    visited[start]=False

        
for i in range(N):
    dfs(i,1)
    if five:
        print(1)
        break
else:
    print(0)

처음 나의 풀이 & 회고

for _ in range(M):
    a,b=map(int,input().split())
    arr[a][b]=1
    arr[b][a]=1
five = False

def dfs(start,depth):
    global five
    visited[start]=True

    if depth==5 :
        five = True
        return
    for j in range(N):
        if arr[start][j]==1 and visited[j] == False :
            dfs(j,depth+1)
    visited[start]=False

처음에 위처럼 작성했는데 자꾸 시간 초과가 발생했다.
알고 보니 간선 정보를 2차원 배열에 넣었는데, 이렇게 되면 연결이 되었는지를 확인하기 위해서는 모든 사람을 조사해 봐야 한다는 차이를 깨달았다.
List를 이용하면, for i in List 처럼 연결된 사람을 바로 확인할 수 있어서 탐색하는 더 빠르다.

여태까지 DFS 간선 정보를 2차원으로만 사용했는데 List를 이용한 좋은 예인 것 같다.