https://www.acmicpc.net/problem/13023
13023번: ABCDE문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.www.acmicpc.net
처음 읽었을 때는 뭔 개소린진 모르겠었는데, 검색해보니 아주 간단한 문제였다.
- A는 B와 친구다.
- B는 C와 친구다.
- C는 D와 친구다.
- D는 E와 친구다.
를 만족하는지 찾는다는 뜻은,
a부터 시작해서 깊이가 4 (총 5개) 인 배열이 있는지 묻는 것이다.
먼져, input을 받아 그래프를 만든다. (친구비를 내지 않는이상 쌍방향그래프일거다)
친구관계가없는 찐따는 당연히 포함되지 않을 것이므로,
친구관계가 하나라도 존재하는 정점을 모두 돌면서, 깊이가 4인 배열을 찾는다.
그리고 하나라도 만족하면, 1을 출력하고 즉시 종료하면 된다.
아이디어만 떠올리면 쉬운 문제였다.
import sysinput=sys.stdin.readlinedef dfs(tmp=[]): if len(tmp)==5:
print(1) exit() for i in graph[tmp[-1]]:
# ttt=(graph[tmp[-1]]) #가장 최근에 추가한 친구의 친구를찾자!
if i not in tmp: dfs(tmp+[i]) return
n,m=map(int,input().split())graph=[[] for _ in range(n)]for _ in range(m):
a,b=map(int,input().split()) graph[a].append(b) graph[b].append(a)
for j in range(len(graph)): if graph[j]: #친구관계가 있는 사람만 탐색
dfs(tmp=[j])print(0)p.s
dfs를 사용할때, 현재 dfs안에서 append를 하게되면 pop을 꼭해줘야한다.!!