[BOJ] ABCDE 13023

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

 

1. 문제 이해 및 해결과정

- DFS의 깊이를 구하는 문제  - 깊이가 4이상인가?

2. 풀이방법

 1.DFS

#ABCDE
#https://www.acmicpc.net/problem/13023
import sys
sys.stdin = open("input.txt","r")
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
def DFS(v,depth):
    global flag
    visited[v]=1
    if depth>=4: #깊이가 4이상이면 참
        flag=1
        return

    for i in adj[v]:
        if visited[i]==0:
            DFS(i,depth+1)
            visited[i]=0 #다음 방문시 처리를 위해
            if flag==1:
                return

if __name__=="__main__":
    n,m=map(int,input().split())
    adj = [[] * n for _ in range(n)]
    visited = [0] * (n)
    for _ in range(m):
        a,b=map(int,input().split())
        #adj[a][b]=adj[b][a]=1
        adj[a].append(b)
        adj[b].append(a)

  #  for x in adj:
  #      print(x)
    flag=0
    for i in range(n): #시작점
        DFS(i,0)
        visited[i]=0 #visited배열을 매번 만드는 것보다 다쓰고 0으로 초기화하면 메모리 아낌
        if flag==1:
            break

    print(flag)

 

3. 오답원인

 1. 시간초과 -오답코드

#ABCDE
#https://www.acmicpc.net/problem/13023
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
def DFS(v,depth):
    global flag
    visited[v]=1
    if depth>=4: #깊이가 4이상이면 참
        flag=1
        return

    for i in range(n):
        if visited[i]==0 and adj[v][i]==1: #방문안했고 연결되어 있으면
            DFS(i,depth+1)
            visited[i]=0 #다음 방문시 처리를 위해

if __name__=="__main__":
    n,m=map(int,input().split())
    adj = [[0] * n for _ in range(n)]
    visited = [0] * (n)
    for _ in range(m):
        a,b=map(int,input().split())
        adj[a][b]=adj[b][a]=1

    flag=0
    for i in range(n):
        DFS(i,0)
        visited[i]=0 #visited배열을 매번 만드는 것보다 다쓰고 0으로 초기화하면 메모리 아낌
        print(visited)
        if flag==1:
            break

    print(flag)

- 문제점1. 가지치기 깊이가 4이상이면 더이상 해 볼 필요가 없다. 

  for x in adj:
        print(x)

 - 문제점2. adj 에 인접행렬 배열을 만들었었는데 각 행에 연결된 정점만 추가하고 DFS에서 for문을 그 시작점과 연결된 정점 만큼만 돌리면 된다

  for _ in range(m):
        a,b=map(int,input().split())
        #adj[a][b]=adj[b][a]=1
        adj[a].append(b)
        adj[b].append(a)

 for i in adj[v]:
        if visited[i]==0:
            DFS(i,depth+1)
            visited[i]=0 #다음 방문시 처리를 위해
            if flag==1:
                return

 

4. 알게된 점

 

- 그래프 처리할때 무조건 인접행렬 하는게 아니라 연결된 정점을 저장하는 식으로 풀이할 수 있다. 

 adj = [[] * n for _ in range(n)]
    visited = [0] * (n)
    for _ in range(m):
        a,b=map(int,input().split())
        #adj[a][b]=adj[b][a]=1
        adj[a].append(b)
        adj[b].append(a)

1번 테스트케이스 adj

 

3번 테스트 케이스 adj