백준 13023 ABCDE

이것도 뭔소린지 잘모르겠었는데

첫번째 예제 그림으로 그려보니까 바로 이해됐다

 

그러니까 dfs든 bfs든 한번했는데 한명이라도 연결이 안됐다면 그건 0을 출력하고 전부 연결됐다면 1을 출력하면 된다

이문제는 dfs가 더 적합할듯하다

 

근데 n이 2000이니까 재귀제한 늘려주고 가자 제한은 2500으로 늘려주자

 

import sys

sys.setrecursionlimit(2500)

n,m=map(int,sys.stdin.readline().rstrip().split())
arr=[[0]*n for _ in range(n)]
for i in range(m):
    s,e=map(int,sys.stdin.readline().rstrip().split())
    arr[s][e]=1
    arr[e][s]=1

v=[0]*n

def dfs(node):
    if v[node]==1:
        return
    v[node]=1
    for i in range(n):
        if arr[node][i]==1 and v[i]==0:
            dfs(i)

result=1
for i in range(n):
    if v[i]==0:
        result=0
        break
print(result)

이렇게 작성했는데 예제3에 막힌다

 

다시 생각해보자

 

for문을 끝까지 도는게 아니라 한번만 돌아주자

다시말해 재귀호출을 했으면 바로 종료시키는거다

 

수정하고도 왜 안되나 했는데 dfs호출이 없었다.

코드를 주의깊게 살피자

 

 

 

고려해야될게 몇개 더 있었다

 

이렇게 보니까 위상정렬같아서 위상정렬로만 풀리는건가 했는데 그건 아닌듯하다

 

 

도저히 모르겠어서 접근법만 좀 찾아봤다. 내 접근이 잘못됐던거다. 이렇게가 아니라 한번이라도 깊이가 n이 되면 참인거고 n이 한번도 안됐으면 낙오된 얘가 있다는거다.

 

작성해보자

import sys

sys.setrecursionlimit(2500)

n,m=map(int,sys.stdin.readline().rstrip().split())
arr=[[0]*n for _ in range(n)]
for i in range(m):
    s,e=map(int,sys.stdin.readline().rstrip().split())
    arr[s][e]=1
    arr[e][s]=1


max_deep=[0]
def dfs(node,deep=1):
    if v[node]==1:
        return
    max_deep[0]=max(max_deep[0],deep)
    v[node]=1
    for i in range(n):
        if arr[node][i]==1 and v[i]==0:
            dfs(i,deep+1)

for i in range(n):
    v=[0]*n
    dfs(i)
if max_deep[0]==n:
    print(1)
else:
    print(0)

근데 이것도 예제에서 틀린다

 

이경우에 문제가 생긴다

 

깊이가 5밖에 안되니까 문제가 생긴다.

 

아 깊이가 n이 되게 하는 문제가 아닌가보다

저 왼쪽 그래프는 오른쪽과 같이 표현이 되는데 이건 뭘 어떻게 해도 한붓그리기가 안된다.

따라서 문제를 다시읽어봤고 a,b,c,d,e라고만 되어있다.

그렇다 깊이가 5가되면 출력하는거다.

 

문해력이슈였다..

 

import sys

sys.setrecursionlimit(2500)

n,m=map(int,sys.stdin.readline().rstrip().split())
arr=[[0]*n for _ in range(n)]
for i in range(m):
    s,e=map(int,sys.stdin.readline().rstrip().split())
    arr[s][e]=1
    arr[e][s]=1


max_deep=[0]
def dfs(node,deep=1):
    if v[node]==1:
        return
    max_deep[0]=max(max_deep[0],deep)
    v[node]=1
    for i in range(n):
        if arr[node][i]==1 and v[i]==0:
            dfs(i,deep+1)

for i in range(n):
    v=[0]*n
    dfs(i)
if max_deep[0]>=5:
    print(1)
else:
    print(0)

이대로 제출

좀 더 생각해보자

깊이가 5넘으면 함수 종료시키자

import sys

sys.setrecursionlimit(2500)

n,m=map(int,sys.stdin.readline().rstrip().split())
arr=[[0]*n for _ in range(n)]
for i in range(m):
    s,e=map(int,sys.stdin.readline().rstrip().split())
    arr[s][e]=1
    arr[e][s]=1


max_deep=[0]
def dfs(node,deep=1):
    if v[node]==1:
        return
    max_deep[0]=max(max_deep[0],deep)
    v[node]=1
    if max_deep[0]>=5:
        return
    for i in range(n):
        if arr[node][i]==1 and v[i]==0:
            dfs(i,deep+1)

for i in range(n):
    v=[0]*n
    dfs(i)
    if max_deep[0]>=5:
        break
if max_deep[0]>=5:
    print(1)
else:
    print(0)

또 어딜 고쳐봐야할까

 

가장 먼저 의심해야할건 재귀가 쓸데없이 반복될 가능성부터 생각해봐야한다

수정에 수정을 거듭하고 좀 검색해본 결과

알아냈다

내 코드는 유효한 간선을 탐색을 해야하는데 이렇게 작성하면 최대 2000번의 탐색이 또 될수있으니

이부분을 고치기 위해서

간선의 개수만큼만 탐색하게 수정하자

드디어 시간초과가 아니다!!!!

 

이건 뭐가 틀렸는지 알지 노드탐색시 방문해제를 해줘야한다

import sys

sys.setrecursionlimit(2500)

n,m=map(int,sys.stdin.readline().rstrip().split())
arr=[[] for _ in range(n)]
for i in range(m):
    s,e=map(int,sys.stdin.readline().rstrip().split())
    arr[s].append(e)
    arr[e].append(s)


max_deep=[0]
def dfs(node,deep=1):
    if v[node]==1:
        return
    max_deep[0]=max(max_deep[0],deep)
    v[node]=1
    if max_deep[0]>=5:
        return
    for i in arr[node]:
        if v[i]==0:
            dfs(i,deep+1)
            if deep>=5:
                break
            v[i]=0

for i in range(n):
    v=[0]*n
    dfs(i)
    if max_deep[0]>=5:
        break
if max_deep[0]>=5:
    print(1)
else:
    print(0)

힘든싸움이었다.