EDOC 2022.08 3주차

Union find 알고리즘

https://brownbears.tistory.com/460

[Python] union find (disjoint-set) 알고리즘

 

---

 <백준 1043번 거짓말>

https://blockdmask.tistory.com/569

find() 함수

[python] 파이썬 find 함수에 대해서

list(range(N+1))

안에 0부터 N까지의 수가 들은 리스트를 만들어낸다.

 

for _ in range()

값을 무시하고 싶을 때 쓰는 것 같다

https://mingrammer.com/underscore-in-python/

파이썬 언더스코어(_)에 대하여

from sys import stdin
N, M = map(int, stdin.readline().split()) # 사람수, 파티수
parent = list(range(N+1)) #각 인덱스 번호의 parent번호
Truelist = list(map(int, stdin.readline().split()))[1:] # 진실아는사람 번호
allParty = [] # 파티의 모음

for _ in range(M):# 파티 수
    partylist = list(map(int, stdin.readline().split()))
    allParty.append(partylist) # 거짓말 할 수 있는 파티 찾을 때 

    for i in range(partylist[0]-1): # 사람들 페런트 잇기
        A = 0
        B = 0
        num = partylist[i+1]
        while(1):
            if num == parent[num]:
                A = num
                break
            else:
                num = parent[num]
                
        num = partylist[i+2]
        while(1):
            if num == parent[num]:
                B = num
                break
            else:
                num = parent[num]

        if A and B in Truelist:
            pass

        elif A in Truelist:
            parent[B] = A

        elif B in Truelist:
            parent[A] = B

        else:
            if A < B:
                parent[B] = A
        
            else:
                 parent[A] = B

result=0
for party in allParty: # 거짓말 할 수 있는 파티 찾기
    for i in range(party[0]): #각 파티의 참가사람 부모가 트루리스트 안에 있는지
        num = party[i+1]
        while(1):
            if num == parent[num]:
                if num in Truelist:
                    result += 1
                    break
                else:
                    break
            else:
                num = parent[num]

# 결과
print(result)

유니언 파인드 알고리즘을 어떻게 쫌 이해해봐서짯는데

쩬짱돌아가긴돌아가는데값이이상하게나온다오류나면고치면되는데이건논리가어디가틀린건지반복문이3개겹쳐있어서프린트로중간중간찍어봐서알아낼엄두도안난다하내2시간폐기..

반복문은 2개까지만 겹치는 걸로 하고 앞으로는 함수를 적극 활용해야겠다..

 

다시

사실을 아는 집단에 있는 사람이 있는 파티는 제외하고, 그 파티에 있던 다른 사람이 있는 파티도 제외해야 한다. 

각 파티마다 사실집단이랑 교집합이 있는지 비교해서 있으면 사실집단에 그 파티집단 합집합해버리고

다시 파티 다 돌면서 완성된 사실집합에 사람들 있는지 비교하면도ㅣㄴ따!

 

https://pydole.tistory.com/80

[Python] set 자료형 - 교집합, 합집합, 차집합

from sys import stdin
N, M = map(int, stdin.readline().split()) # 사람수, 파티수
Trueset = set(list(map(int, stdin.readline().split()))[1:]) # 진실아는사람 번호
allParty = [] # 파티의 모음

for _ in range(M):# 사실집단 완성하기
    partyset = set(list(map(int, stdin.readline().split()))[1:])
    allParty.append(partyset) # 거짓말 할 수 있는 파티 찾을 때 
    if len(partyset.intersection(Trueset)) > 0: # 파티에 사실을 아는 자가 있는가?
        Trueset = Trueset.union(partyset) # 그러면 모두가 사실을 아는 것으로 간주

result = 0
for party in partyset: # 완성된 사실알집단과 파티 참석인원 비교
    if len(party.intersection(Trueset)) > 0:
        pass
    else:
        result += 1

print(result)

'int' object has no attribute 'intersection'오류

뭐가 잘못됐단거지

from sys import stdin
N, M = map(int, stdin.readline().split()) # 사람수, 파티수
Trueset = set(list(map(int, stdin.readline().split()))[1:]) # 진실아는사람 번호
allParty = [] # 파티의 모음

for _ in range(M):# 사실집단 완성하기
    partyset = set(list(map(int, stdin.readline().split()))[1:])
    allParty.append(partyset) # 거짓말 할 수 있는 파티 찾을 때 
    if len(partyset.intersection(Trueset)) > 0: # 파티에 사실을 아는 자가 있는가?
        Trueset = Trueset.union(partyset) # 그러면 모두가 사실을 아는 것으로 간주

result = 0
for party in partyset: # 완성된 사실알집단과 파티 참석인원 비교
    if len(allParty.intersection(Trueset)) > 0:
        pass
    else:
        result += 1

print(result)

ㅎㅎ allParty 넣어야 하는데 partyset 넣었다ㅎㅎ

모든 예제가 맞게 돌아가고! 논리적으로 다 맞는 것 같다!

근데! 백준에서 틀렸다고 한다

아니 예제 7개 다 맞게 나오는데 대체

 

주석을 다 없애고 돌렸더니 런타임에러나온다

휴..

으으]다음에다시해보겠다..

 

우리 조 풀이 사이트

https://www.notion.so/0beca97416764c9ba28c38fb1c1e8f08?v=dc3d169abe454df0a4e73453a09f80aa&p=034d2d55283a4d57842696479c1a4e08&pm=s 

---

최단 경로 

https://velog.io/@kyunghwan1207/최단-경로-알고리즘

최단 경로 알고리즘

우선순위 큐

 

 데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거하는 독특한 특성을 지닌 자료구조입니다.

https://www.daleseo.com/python-priority-queue/

파이썬의 우선순위 큐(PriorityQueue) 사용법

 

다익스트라 알고리즘

https://justkode.kr/algorithm/python-dijkstra

Python으로 다익스트라(dijkstra) 알고리즘 구현하기

??

---

<백준 1446번 지름길>

https://velog.io/@heyksw/Python-백준-silver-1446-지름길

[Python] 백준 / silver / 1446 : 지름길

다익스트라알고리즘..모르겠다,,BFS 탐색은 쫌 이해할 수 있었다

https://fre2-dom.tistory.com/144

[baekjoon] 백준 1446번(파이썬): 지름길

BFS 탐색은 쫌 이해할 수 있었다

알고리즘 강의로 한번 공부하면 이해하기 쉬워질려나?

 

graph = [list(map(int, input().split())) for _ in range(n)]

dis = [i for i in range(d+1)]

처럼 그냉 안에 반복문 넣으면 알아서 돌아가는구나

from sys import stdin

D, N = map(int, stdin.readline().split()) 
shortcut = [list(map(int, stdin.readline().split()) ) for _ in range(D)]
road = list(i for i in range(N+1))

for i in range(N+1):
    road[i] = min(road[i], road[i-1]+1)
    for f,e,len in shortcut:
        if i == f and e <= N and road[i]+len < road[e]: #역주행 불가,더 짧은 길만
            road[e] = road[i]+len
print(road[N])

 

다른 분 거 보구~ㅎㅎ 감사합니다 아이고 어려워라

 우리 조 풀이

https://www.notion.so/0beca97416764c9ba28c38fb1c1e8f08?v=dc3d169abe454df0a4e73453a09f80aa&p=97d4db71c1e648ac85dd607ff3d282bc&pm=s 

다들 인터넷 참고하셧다구 한다

어려운 문제엿꾼..

 

장난아니었지만 유익했다! 덕분에 백준레벨 골드 문제도 풀어보고 이독짱~