n=list(map(int,input().split()))
land=n[0]
bridge=n[1]
start=n[2]
bridegeinfo=[]
footprint=[]
visited=[0]*land
for i in range(bridge):
li=set(map(int,input().split())) #양방향이니까 set으로 저장
bridegeinfo.append(li)
visited[start-1]=1
footprint.append(start) #start 저장
def DFS(start):
#visited[start-1]=1 #시작점은 방문했다
#footprint.append(start)
for i in bridegeinfo: #리스트 전체 탐색
ex=i-{start} #나머지 요소만 남은 집합(차집합 수행)
ex=list(ex)
for j in (ex):
last=j
if (start in i) and (visited[last-1]==0): #집합에 start가 있고 아직 방문 안 한 곳이라면
visited[last-1]=1 #다음 노드 방문했다고 고치고
footprint.append(last) #방문기록
#집합의 다른 요소에 접근하기 위해 현 요소를 지우고 나머지 요소를 취함
DFS(last)
#재귀끝내고와서 백트래킹으로 다시 원래
bridegeinfo.remove(i) #이미 쓴 간선은 지워주는 게
return
DFS(start)
print(footprint)근데 아직 숫자 작은 거부터 방문하는 건 구현 안 함
잘못된 코드
n=list(map(int,input().split()))
land=n[0]
bridge=n[1]
start=n[2]
bridegeinfo=[]
footprint=[]
visited=[0]*land
for i in range(bridge):
li=set(map(int,input().split())) #양방향이니까 set으로 저장
bridegeinfo.append(li)
#visited[start-1]=1
#footprint.append(start) #start 저장
def DFS(start):
visited[start-1]=1 #시작점은 방문했다
#footprint.append(start)
for i in bridegeinfo: #리스트 전체 탐색
ex=i-{start} #나머지 요소만 남은 집합(차집합 수행)
ex=list(ex)
for j in (ex):
last=j
if (start in i) and (visited[last-1]==0): #집합에 start가 있고 아직 방문 안 한 곳이라면
visited[start-1]=1 #방문했다고 고치고
footprint.append(start) #방문기록
#집합의 다른 요소에 접근하기 위해 현 요소를 지우고 나머지 요소를 취함
DFS(last)
#재귀끝내고와서 백트래킹으로 다시 원래
bridegeinfo.remove(i) #이미 쓴 간선은 지워주는 게
return
DFS(start)
print(footprint)
1이 마지막에 저장이 안 됨
왜냐면 start last 방문 저장, visited 수정하는 과정에서 잠깐 소란이...
DFS는 last (1)로 하면서 다음 재귀 때 visit했다고 고치고 그 뒤로 1을 append한다는 코드가 없잖냐
성공
n=list(map(int,input().split()))
land=n[0]
bridge=n[1]
start=n[2]
bridegeinfo=[]
footprint=[]
visited=[0]*land
for i in range(bridge):
li=set(map(int,input().split())) #양방향이니까 set으로 저장
bridegeinfo.append(li)
visited[start-1]=1
footprint.append(start) #start 저장
def DFS(start):
#visited[start-1]=1 #시작점은 방문했다
#footprint.append(start)
number=[] #목적지 크기 비교할 곳
for i in bridegeinfo: #리스트 전체 탐색
ex=i-{start} #나머지 요소만 남은 집합(차집합 수행)
ex=list(ex)
for j in (ex):
last=j
if (start in i) and (visited[last-1]==0): #집합에 start가 있고 아직 방문 안 한 곳이라면
visited[last-1]=1 #다음 노드 방문했다고 고치고
i=list(i) #리스트로 만들고
if i[0]==last:
i[0],i[1]=i[1],i[0]
number.append(i[:]) #간선
number.sort() #이제 여기서 작은 수부터
for i in number: #간선들
footprint.append(i[1]) #방문기록
#집합의 다른 요소에 접근하기 위해 현 요소를 지우고 나머지 요소를 취함
DFS(i[1])
#재귀끝내고와서 백트래킹으로 다시 원래
#bridegeinfo.remove(i) #이미 쓴 간선은 지워주는 게 근데 여기선 브릿지인포의 집합이랑 넘버의 리스트는 순서가 다를 수도 있으니 못 씀
#[1,2] [2,1)]
return
DFS(start)
print(footprint)
set 양방향
양방향이니까 set로 했는데 중간에 리스트랑 뭐 할 때 ㅈㄴ 귀찮네 집합말고 다른 방법도 있나?
와틀렸었네
찐성공
n=list(map(int,input().split()))
land=n[0]
bridge=n[1]
start=n[2]
bridegeinfo=[]
footprint=[]
visited=[0]*land
for i in range(bridge):
li=set(map(int,input().split())) #양방향이니까 set으로 저장
bridegeinfo.append(li)
visited[start-1]=1
footprint.append(start) #start 저장
def DFS(start):
#visited[start-1]=1 #시작점은 방문했다
#footprint.append(start)
number=[] #목적지 크기 비교할 곳
for i in bridegeinfo: #리스트 전체 탐색
ex=i-{start} #나머지 요소만 남은 집합(차집합 수행)
ex=list(ex)
for j in (ex):
last=j #집합의 나머지 요소 빼내기
if (start in i) and (visited[last-1]==0): #집합에 start가 있고 아직 방문 안 한 곳이라면
print(start)
i=list(i) #리스트로 만들고
if i[0]==last:
i[0],i[1]=i[1],i[0]
number.append(i[:]) #간선
number.sort() #이제 여기서 작은 수부터 오야근데 이게 정렬이 되네 안에 있는 건 리스트 안의 리스트인데
for i in number: #간선들
if (visited[i[1]-1]==0):
visited[i[1]-1]=1 #다음 노드 방문했다고 고치고
footprint.append(i[1]) #방문기록
#집합의 다른 요소에 접근하기 위해 현 요소를 지우고 나머지 요소를 취함
DFS(i[1])
#재귀끝내고와서 백트래킹으로 다시 원래
#bridegeinfo.remove(i) #이미 쓴 간선은 지워주는 게 근데 여기선 브릿지인포의 집합이랑 넘버의 리스트는 순서가 다를 수도 있으니 못 씀
#[1,2] [2,1)]
return
바뀐 부분
for i in number: #간선들
if (visited[[i[1]-1]==0):
visited[i[1]-1]=1number 읽을 때 조건 추가
number에 추가되는 간선은 start 포함한 거면 다 저장되는데 그 중에서 방문했는지 안 했는지 확인 안 하면 중복 방문될 수 있음
사실 위에 간선을 number에 추가할 때 visited를 바꿔버리면 나중에 number 탐색해서 진짜 방문할 때 이미 visited가 바뀌어있어서 오류남
case3 BFS 오류
for i in range(land):
if visited1[i]==0: #아무 방문 안 한 노드
BFS(i)예제 3의 경우 랜드가 1000개인데 간선은 999와 1000을 잇는 거 하나.
근데 저대로 탐색한다면 불필요한 재귀를 엄청 많이 하게 됨. visited에 이미 1000개의 0이 있고 그뒤로도 999,998개의 0이 있으니 그만큼 재귀를 하면..........
수정
n=list(map(int,input().split()))
land=n[0]
bridge=n[1]
start=n[2]
bridegeinfo=[]
footprint=[]
visited=[0]*land
for i in range(bridge):
li=set(map(int,input().split())) #양방향이니까 set으로 저장
bridegeinfo.append(li)
visited[start-1]=1
footprint.append(start) #start 저장
def DFS(start):
#visited[start-1]=1 #시작점은 방문했다
#footprint.append(start)
number=[] #목적지 크기 비교할 곳
for i in bridegeinfo: #리스트 전체 탐색
ex=i-{start} #나머지 요소만 남은 집합(차집합 수행)
ex=list(ex)
for j in (ex):
last=j #집합의 나머지 요소 빼내기
if (start in i) and (visited[last-1]==0): #집합에 start가 있고 아직 방문 안 한 곳이라면
print(start)
i=list(i) #리스트로 만들고
if i[0]==last:
i[0],i[1]=i[1],i[0]
number.append(i[:]) #간선
number.sort() #이제 여기서 작은 수부터 오야근데 이게 정렬이 되네 안에 있는 건 리스트 안의 리스트인데
for i in number: #간선들
if (visited[i[1]-1]==0):
visited[i[1]-1]=1 #다음 노드 방문했다고 고치고
footprint.append(i[1]) #방문기록
#집합의 다른 요소에 접근하기 위해 현 요소를 지우고 나머지 요소를 취함
DFS(i[1])
#재귀끝내고와서 백트래킹으로 다시 원래
#bridegeinfo.remove(i) #이미 쓴 간선은 지워주는 게 근데 여기선 브릿지인포의 집합이랑 넘버의 리스트는 순서가 다를 수도 있으니 못 씀
#[1,2] [2,1)]
return
footprint1=[]
visited1=[0]*land
visited1[start-1]=1
footprint1.append(start) #start 저장
def BFS(start):
number1=[]
for i in bridegeinfo:
ex=i-{start} #ex는 전부 다 만들어짐
ex=list(ex)
for j in (ex):
last=j
if (start in i) and (visited1[last-1]==0):
visited1[last-1]=1
i=list(i)
if i[0]==last: #출발지 start가 앞으로 가게 바꿔야 편함
i[0],i[1]=i[1],i[0]
number1.append(i[:])
if len(number1)>1:
number1.sort()
for i in number1:
footprint1.append(i[1])
for i in bridegeinfo: #간선 중에
i=list(i)
if visited1[i[0]-1]==0: #아무 방문 안 한 노드
BFS(i[0])
elif visited1[i[1]-1]==0:
BFS(i[1])
DFS(start)
BFS(start)
print(footprint)
print(footprint1)