255. 케빈 베이컨 법칙
1) 어떤 전략(알고리즘)으로 해결?
- bfs, 트리 탐색
2) 코딩 설명
<내 풀이>
from collections import deque
import sys
sys.setrecursionlimit(10**5)
n,m = map(int, sys.stdin.readline().split())
people = []
for i in range(n+1) :
people.append([])
def find_parent(target) :
cand = deque()
cand.append(target)
while cand :
now = cand.popleft()
for idx in range(len(people[now])) :
if visit[people[now][idx]]==0 :
visit[people[now][idx]] = visit[now]+1
cand.append(people[now][idx])
for i in range(m) :
p1,p2 = map(int, sys.stdin.readline().split())
people[p1].append(p2) # 1단계만에 서로 아는 아이들
people[p2].append(p1)
bacon = []
for ii in range(1,n+1) : # 각행마다 돌아주면서
# 그 행의 관계들 쭉 검사용
visit = [0 for _ in range(n+1)]
visit[ii] = 0
find_parent(ii)
bacon.append(sum(visit))
print(bacon.index(min(bacon))+1)
- 이차원 배열로 처리하지 말고 각자 배열로 만들어서 필요한 애들만 append 하고 따로 remove 안하고 visit 으로 처리하자 !
<내 틀렸던 풀이, 문제점>
15 프로에서 시간초과 나는 풀이
import sys
sys.setrecursionlimit(10**5)
def find_parent(ii, p) :
global cnt
for pp in range(1,m+1) :
if people[p][pp]==1 :
if pp==ii :
return cnt
else :
cnt+=1
find_parent(pp,p)
n,m = map(int, sys.stdin.readline().split())
people=list([0 for _ in range(m+1)] for _ in range(m+1))
for i in range(m) :
p1,p2 = map(int, sys.stdin.readline().split())
people[p1][p2] = 1 # 1단계만에 서로 아는 아이들
people[p2][p1] = 1
for ii in range(1,m+1) :
for p in range(1,m+1) :
if p!=ii and people[ii][p] == 0 :
cnt = 1
find_parent(ii, p)
people[ii][p]+=cnt
cmp = 100000000
for pe in range(1,m) :
if sum(people[pe]) < cmp :
cmp = sum(people[pe])
answer = pe
print(answer)
걍 이건 30프로에서 틀려버린! 풀이
import sys
sys.setrecursionlimit(10**5)
def find_parent(ii, p) :
global cnt
for pp in range(1,m+1) :
if people[p][pp]==1 :
if pp==ii :
return cnt
else :
cnt+=1
find_parent(pp,p)
n,m = map(int, sys.stdin.readline().split())
people=list([0 for _ in range(m+1)] for _ in range(m+1))
for i in range(m) :
p1,p2 = map(int, sys.stdin.readline().split())
people[p1][p2] = 1 # 1단계만에 서로 아는 아이들
people[p2][p1] = 1
for ii in range(1,m+1) :
for p in range(1,m+1) :
if p!=ii and people[ii][p] == 0 :
cnt = 1
find_parent(ii, p)
people[ii][p]+=cnt
people[p][ii]+=cnt
cmp = 100000000
for pe in range(1,m) :
if sum(people[pe]) < cmp :
cmp = sum(people[pe])
answer = pe
print(answer)
10프로 대에서 시간초과 ㅠㅠ
import sys
sys.setrecursionlimit(10**5)
def find_parent(target, chk, cnt, visit) :
global res
cand = []
for pp in range(1,m+1) : # chk 행 조사하는 것
if people[chk][pp]==1 and visit[pp]==0:
cand.append(pp)
for c in cand :
if c==target :
if cnt<res :
res = cnt
return
else :
visit[c] = 1
find_parent(target,c, cnt+1, visit)
visit[c] = 0 # 꼭 방문 체크 풀어주자
n,m = map(int, sys.stdin.readline().split())
people=list([0 for _ in range(m+1)] for _ in range(m+1))
for i in range(m) :
p1,p2 = map(int, sys.stdin.readline().split())
people[p1][p2] = 1 # 1단계만에 서로 아는 아이들
people[p2][p1] = 1
for ii in range(1,m+1) :
for p in range(1,m+1) :
if p!=ii and people[ii][p] == 0 :
res = 5001
visit = [0 for _ in range(m+1)]
find_parent(ii, p, 1, visit)
people[ii][p]=res
people[p][ii]=res
cmp = 1000000000000000000000000
for peop in people :
print(peop)
for pe in range(1,m) :
if sum(people[pe]) < cmp :
cmp = sum(people[pe])
answer = pe
print(answer)
시간초과 해결하기 위해 bfs 로 고쳤는데 30% 틀림 ㅂㄷㅂㄷ
from collections import deque
import sys
sys.setrecursionlimit(10**5)
def find_parent(target, chk, cnt, visit) :
global res
cand = deque()
cand.append((chk, cnt, visit))
while cand :
now = cand.pop()
if now[0]==target :
if now[1]<res :
res = now[1]
return
else :
for pp in range(1,m+1) : # chk 행 조사하는 것
if people[now[0]][pp]==1 and now[2][pp]==0:
now[2][pp] = 1
cand.append((pp, now[1]+1, now[2]))
n,m = map(int, sys.stdin.readline().split())
people=list([0 for _ in range(m+1)] for _ in range(m+1))
for i in range(m) :
p1,p2 = map(int, sys.stdin.readline().split())
people[p1][p2] = 1 # 1단계만에 서로 아는 아이들
people[p2][p1] = 1
for ii in range(1,m+1) :
for p in range(1,m+1) :
if p!=ii and people[ii][p] == 0 :
res = 5001
visit = [0 for _ in range(m+1)]
find_parent(ii, p, 0, visit)
people[ii][p]=res
people[p][ii]=res
cmp = 1000000000000000000000000
# for peop in people :
# print(peop)
for pe in range(1,m) :
cmptarget = sum(people[pe])
if cmptarget < cmp :
cmp = cmptarget
answer = pe
print(answer)
일단 예제쪽은 잘 나오는데,, 틀린 부분이 뭘지 빨리,,, 머리 굴려보자 ,,,, 으으 ㅠㅠ
이것두 30프로에서~
from collections import deque
import sys
sys.setrecursionlimit(10**5)
def find_parent(target, chk, cnt, visit) :
global res
cand = deque()
cand.append((chk, cnt, visit))
while cand :
now = cand.pop()
if now[0]==target :
if now[1]<res :
res = now[1]
return
else :
for pp in range(1,n+1) : # chk 행 조사하는 것
if people[now[0]][pp]==1 and now[2][pp]==0:
now[2][pp] = 1
# BFS는 큐에서 뺀 다음이 아닌,
# 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다
cand.append((pp, now[1]+1, now[2]))
n,m = map(int, sys.stdin.readline().split())
people=list([0 for _ in range(n+1)] for _ in range(n+1))
for i in range(m) :
p1,p2 = map(int, sys.stdin.readline().split())
people[p1][p2] = 1 # 1단계만에 서로 아는 아이들
people[p2][p1] = 1
for ii in range(1,n+1) :
for p in range(1,n+1) :
if p!=ii and people[ii][p] == 0 :
res = 5001
visit = [0 for _ in range(n+1)]
find_parent(ii, p, 0, visit)
people[ii][p]=res
people[p][ii]=res
cmp = 1000000000000000000000000
# for peop in people :
# print(peop)
for pe in range(1,n) :
cmptarget = sum(people[pe])
if cmptarget < cmp :
cmp = cmptarget
answer = pe
print(answer)
65 % 에서 틀리는 풀이
위에서는 visit 을 잘못 측정중이었음
그래서 그 부분 고쳤는데 흐음 더 차자보자
from collections import deque
import sys
sys.setrecursionlimit(10**5)
def find_parent(target, chk, cnt, visit) :
global res
cand = deque()
cand.append((chk, cnt, visit))
while cand :
now = cand.pop()
if now[0]==target :
if now[1]<res :
res = now[1]
return
else :
for pp in range(1,n+1) : # chk 행 조사하는 것
if people[now[0]][pp]==1 and now[2][pp]==0:
newvisit = now[2].copy()
newvisit[pp] = 1
# BFS는 큐에서 뺀 다음이 아닌,
# 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다
cand.append((pp, now[1]+1, newvisit))
n,m = map(int, sys.stdin.readline().split())
people=list([0 for _ in range(n+1)] for _ in range(n+1))
for i in range(m) :
p1,p2 = map(int, sys.stdin.readline().split())
people[p1][p2] = 1 # 1단계만에 서로 아는 아이들
people[p2][p1] = 1
for ii in range(1,n+1) :
for p in range(1,n+1) :
if p!=ii and people[ii][p] == 0 :
res = 5001
visit = [0 for _ in range(n+1)]
find_parent(ii, p, 0, visit)
people[ii][p]=res
people[p][ii]=res
cmp = 1000000000000000000000000
# for peop in people :
# print(peop)
for pe in range(1,n) :
cmptarget = sum(people[pe])
if cmptarget < cmp :
cmp = cmptarget
answer = pe
print(answer)로직 바꿀래잉 !!!!!!!!!!
플로이드 와샬 알고리즘
<반성 점>
- 안되는 로직을 붙들고 있던 나에 모습 ,,, (
나의라는 거 알지만 나에라고 쓴 것임 지적 n o , 지금 약간 예민 ㅡㅡ) 너무 한심해!!! - 로직 과감히 바꿔 바꿔 다 바꿔
<배운 점>
질문란에서 발견한 좋은 글
https://www.acmicpc.net/blog/view/70
- 이차원 배열로 처리하지 말고 각자 배열로 만들어서 필요한 애들만 append 하고 따로 remove 안하고 visit 으로 처리하자 !
