11.23 알고리즘 문제풀이

코테 연습

 

BFS/DFS

첫 번째

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

13023번: ABCDE

import sys
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(2001)

N, M = map(int, input().split())
relation = [[] for _ in range(N)]
for _ in range(M):
    p_1, p_2 = map(int, input().split())
    relation[p_1].append(p_2)
    relation[p_2].append(p_1)

def dfs(i, cnt, visited):
    if cnt == 4:
        return True

    visited.append(i)
    for friend in relation[i]:
        if friend not in visited:
            if dfs(friend, cnt+1, visited):
                return True
    visited.pop()
    return False

def solve():
    for i in range(N):
        visited = []
        if dfs(i, 0, visited):
            return 1
    return 0
print(solve())

import sys

n,m = map(int,sys.stdin.readline().split())
adj = [[]for i in range(n)]

for i in range(m):
    a, b = map(int,sys.stdin.readline().split())
    adj[a].append(b)
    adj[b].append(a)

visited = [0 for _ in range(n)]
flag = 0

def dfs(now,cnt):
    global flag
    visited[now]  = 1 

    if cnt == 4:
        flag = 1
        return  
    
    
    for nxt in adj[now]:
        if visited[nxt] != 1:
            dfs(nxt,cnt+1)
            visited[nxt] = 0
    

for i in range(n):
    dfs(i,0)
    visited[i] = 0 
    if flag == 1:
        break

if flag == 1:
    print(1)
else:
    print(0)

문제를 풀면서 고민했던 부분은

dfs로 4층까지 친구관계를 구해야하는데

4층 깊이 탐색을 실패하고 dfs 스택에서 돌아올 때, visited가 원래대로 돌아와야한다는 점이었다.

이 부분을 어떻게 구현할까 고민하다가

시간 복잡도가 여유가 있다고 판단하고 visited를 리스트로 받아서 순차 탐색하는 것으로 정했다.

 

밑에 우수코드를 참고하면 dfs 이후에 visited를 바로 False하는 과정이 있는데

이는 조합과 순열을 재귀함수로 구현할 때(또는 brute-force) 사용했던 방법이라 눈에 익었다.

아쉽게도 이번에 생각하지 못했지만 다음에는 써먹자.