.PNG)
54. 경로 탐색(그래프 DFS)
방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프
로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는
총 6 가지입니다.
▣ 입력설명
첫째 줄에는 정점의 수 N(2<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연
결정보가 주어진다.
▣ 출력설명
총 가지수를 출력한다.
▣ 입력예제 1
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5
▣ 출력예제 1
6
<내 풀이>
어떻게 진행해야 하는지 감이 하나도 안 잡힌다...ㅠㅠ
def DFS(x) :
if x==n:
else :
DFS(x+1, )
if __name__='__main__'
n, m =map(int, input().split())
g=[[0]*(n+1) for _ in range(n+1)]
for i in range(m) :
a, b = map(int, input().split())
g[a][b]=1
g[b][a]=1 #이거는 방향 그래프라서 a=>b순서라 이거는 넣으면 안된다
DFS(0,0)- 방향 하나만 해야돼서 g[b][a]=1 는 넣으면 안된다
<풀이>
[상태트리]
- 한번 방문한 노드는 다시 방문하면 안된다,
그래서 이거 여부 체크하는 체크리스트 만든다 - for문이 돌고 (1,2,3,4,5) 이거 중에 D(x)와 연결된 노드만을 찾는다
- 찾으면 그 노드 사용했다고 체크하고 거기서 D(x+1) 시작,
- 일단 한 노드에서 끝까지 다 왔으면, 다시 되돌아 갈텐데 되돌아 가면서(백하면서) 체크리스트 표시했던 것 다시 체크 없애준다
def DFS(x) :
global cnt
if x==n:
cnt+=1
else :
for i in range(1,n+1) : #n가지로 가지가 뻗어야 되는데 1부터다 0아니고
if g[x][i]==1 and ch[i]==0 : #i가 방문을 안한데고 x에서 a로 갈 수 있다면
ch[i]=1
DFS(i)
ch[i]=0 #다시 back할 때 ch 풀어주는 것
if __name__=='__main__' :
n, m =map(int, input().split())
g=[[0]*(n+1) for _ in range(n+1)]
for i in range(m) :
a, b = map(int, input().split())
g[a][b]=1
cnt=0
ch=[0]*(n+1) # 얘는 체크리스트
ch[1]=1 # 1번에 체크하고
DFS(1) # 1번 노드로 넘어간 것
print(cnt)- 추가적으로 경로까지 나타나게 하고 싶다면
경로 저장해주는 리스트 만들어서 거기다가 i 저장시키면 된다
그런데 다음 DFS 호출한 뒤에는 이거를 pop해줘야 한다
아니면 밑의 결과 나와야 하는데
1 2 3 4 5
1 2 5
1 3 4 2 5
1 3 4 5
1 4 2 5
1 4 5
계속 더해져서
1 2 3 4 5
1 2 3 4 5 5
1 2 3 4 5 5 3 4 2 5
1 2 3 4 5 5 3 4 2 5 5
1 2 3 4 5 5 3 4 2 5 5 4 2 3 5
1 2 3 4 5 5 3 4 2 5 5 4 2 3 5 5
이런 식으로 나온다
def DFS(x) :
global cnt
if x==n:
for i in path:
print(i ,end=' ')
print()
cnt+=1
else :
for i in range(1,n+1) :
if g[x][i]==1 and ch[i]==0 :
ch[i]=1
path.append(i)
DFS(i)
path.pop() #해서 마지막에 넣어줬던 것 빼줘야 한다,
ch[i]=0
if __name__=='__main__' :
n, m =map(int, input().split())
g=[[0]*(n+1) for _ in range(n+1)]
for i in range(m) :
a, b = map(int, input().split())
g[a][b]=1
path=[] #경로 저장해주는 리스트
path.append(1) #경로의 일번은 무조건 1이라서 append
cnt=0
ch=[0]*(n+1)
ch[1]=1
DFS(1)
print(cnt)
- 인접리스트로 이 문제를 해결했을 때
(노드 갯수가 많아지면 인접행렬로는 안되고 인접리스트를 써야 한다)
def DFS(v):
global cnt
if v==n:
cnt+=1
else:
for nv in g[v]:
if ch[nv]==0:
ch[nv]=1
DFS(nv)
ch[nv]=0
if __name__=="__main__":
n, m=map(int, input().split())
g=[[] for _ in range(n+1)]
ch=[0]*(n+1)
for i in range(m):
a, b=map(int, input().split())
g[a].append(b)
cnt=0
ch[1]=1
DFS(1)
print(cnt)
<반성점>
- 저번에 쓰인 ch 여기서 또 쓰인다, 자주 쓰인다
- range 돌 때 얘가 1부터 돌아야 되는지, 아님 처음(0)부터 돌아야 하는지 잘 체크
- 백할때 체크리스트에 체크해놨던 거 풀어주는 부분 매우 생소
- 자꾸 ==인데 = 쓰지마라
<배운 점>
- ch DFS 뒤에 없애줘야해 BACK할 때
- 만약 경로까지 구하라고 할 때 리스트 만들어서 거기에 저장하는데, DFS호출하고 난 뒤 back할 때에는 에는 pop해서 없애줘야한다
<2회독 내 풀이> - 실패! DFS(x+1) 아니고 DFS(i)
def DFS(x) :
global cnt
if x==n:
cnt+=1
return()
else :
for i in range(1,n+1) :
if ch[i]==0 and g[x][i]==1:
ch[i]=1
DFS(x+1) ###이 부분 틀림
ch[i]=0
if __name__=='__main__' :
n, m = map(int, input().split())
g=[[0]*(n+1) for _ in range(n+1)]
for i in range(m):
a, b = map(int, input().split())
g[a][b]=1
cnt=0
ch=[0]*(n+1)
ch[1]=1
DFS(1)
print(cnt)
<신경 써야 할 부분>
else :
for i in range(1,n+1) :
if ch[i]==0 and g[x][i]==1:
#체크리스트에 표시 안돼있어야 하고 동시에 경로도 맞아줘야 한다
ch[i]=1
DFS(i) ===>왜냐면 g[x][i] 에서 x에서 i로 이동하잖아!
ch[i]=0 ===>i도 다시 풀어주기
if name=='main' :
n, m = map(int, input().split())
g=[[0](n+1) for _ in range(n+1)]
for i in range(m):
a, b = map(int, input().split())
g[a][b]=1 ===> 방향이 하나뿐이다
cnt=0
ch=[0](n+1)
ch[1]=1 #===> 1 이미 방문했다!
DFS(1) ===> 그리고 나서 다음 노드로 넘어간 것
print(cnt)
- 경로까지 추가할 때 꼭 DFS호출하고
ch 초기화할 때 res도 초기화 해주어야 한다
else :
for i in range(1,n+1) :
if ch[i]==0 and g[x][i]==1:
ch[i]=1
res[x]=i
DFS(i)
ch[i]=0
res[x]=0
그리고 처음에
res=[0]*(n+1)
res[0]=1 ==>왜냐면 이미 DFS가 1을 거쳤음을 가정하기 때문에
DFS(1)
print(cnt)
