백준 검색 결과
248 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 9372번: 상근이의 여행 (Python)

접근 처음 문제를 보자마자 답은 n - 1 인 것을 알았다. 그래도 탐색을 통해 답을 구하는 방법이 없을까 고민하여 BFS 알고리즘을 이용하여 풀게 되었다. BFS 알고리즘을 통해 순환하면서 새로운 경로를 통해 새로운 정점을 만나면 카운트해주는 방법이다. 코드 import sys def bfs(x): q = [x] visited[x] = 1 cnt = 0 while q: now = q.pop(0) for nx in air[now]: if visited[nx] == 0: visited[nx] = 1 cnt += 1 q.append(nx) return cnt for _ in range(int(sys.stdin.readline())): n, m = map(int, sys.stdin.readline().spli..

2021. 5. 2. 02:03
코딩/백준 (Python)

백준 20040번: 사이클 게임 (Python)

접근 이번 문제에서는 유니온파인드 알고리즘을 이용하여 풀 수 있다. 유니온파인드 알고리즘 설명: 2021.05.01 - [코딩/백준 (Python)] - 백준 1717번: 집합의 표현 (Python) 백준 1717번: 집합의 표현 (Python) 접근 파인드유니온 알고리즘을 모르지만 일단 구현되게 하여 풀기는 하였다. 하지만 파인드유니온 알고리즘을 처음 접했으니 제대로 공부하고 최적화 방법도 알아보고 코드를 다시 작성해보았 ca.ramel.be 유니온파인드 알고리즘을 수행하면서 i 번째 단계에서 주어진 두개의 수의 루트 노드가 같으면 싸이클이 이루어지므로 i를 출력해주고 연산을 마친다. 코드 import sys def find(x): if connect[x] < 0: return x p = find(co..

2021. 5. 2. 01:18
코딩/백준 (Python)

백준 4195번: 친구 네트워크 (Python)

접근 유니온파인드 알고리즘을 이용하여 풀 수 있다. 유니온파인드 알고리즘 설명: 2021.05.01 - [코딩/백준 (Python)] - 백준 1717번: 집합의 표현 (Python) 백준 1717번: 집합의 표현 (Python) 접근 파인드유니온 알고리즘을 모르지만 일단 구현되게 하여 풀기는 하였다. 하지만 파인드유니온 알고리즘을 처음 접했으니 제대로 공부하고 최적화 방법도 알아보고 코드를 다시 작성해보았 ca.ramel.be 여기서는 weighted union find를 사용하지 않고 대신 문자형을 받을 수 있는 dictionary를 두개 사용하여 문제를 해결하였다. 기존 리스트들의 역할을 하는 딕셔너리와 집합의 크기를 나타내는 딕셔너리를 각각 이용했다. 코드 import sys def find(x)..

2021. 5. 1. 22:47
코딩/백준 (Python)

백준 1976번: 여행 가자 (Python)

접근 유니언파인드 알고리즘을 이용하여 풀 수 있다. 알고리즘에 대해서는 이전 글에서 자세하게 설명하여 링크를 남기도록 한다. 유니언파인드 알고리즘 설명: 2021.05.01 - [코딩/백준 (Python)] - 백준 1717번: 집합의 표현 (Python) 백준 1717번: 집합의 표현 (Python) 접근 파인드유니온 알고리즘을 모르지만 일단 구현되게 하여 풀기는 하였다. 하지만 파인드유니온 알고리즘을 처음 접했으니 제대로 공부하고 최적화 방법도 알아보고 코드를 다시 작성해보았 ca.ramel.be 연결된 도시들끼리 유니언을 이용하여 집합을 만들어주고, 주어진 여행경로들이 같은 루트 노드를 가지고 있는지를 체크해주면 된다. 코드 import sys def find(x): if connect[x] < 0..

2021. 5. 1. 20:49
코딩/백준 (Python)

백준 1717번: 집합의 표현 (Python)

접근 파인드유니온 알고리즘을 모르지만 일단 구현되게 하여 풀기는 하였다. 하지만 파인드유니온 알고리즘을 처음 접했으니 제대로 공부하고 최적화 방법도 알아보고 코드를 다시 작성해보았다. 유니온 파인드 알고리즘이란? 그래프 알고리즘의 일종으로 상호배타적 집합, Disjoint-set이라고도 한다. 여러 노드가 존재할 때 어떤 두개의 노드를 묶어주고, 또 어떤 두 노드가 같은 집합에 속해있는지 확인하는 알고리즘이다. FIND: 노드 x가 어느 집합에 포함되어 있는지 찾는 연산 UNION: 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산 유니온 파인드 구현 트리를 통해서 유니온파인드가 구현될 수 있다. parent[i] 리스트를 작성하여 i노드의 부모노드라고 정의하고 초기화해준다. parent[i..

2021. 5. 1. 11:46
코딩/백준 (Python)

백준 4803번: 트리 (Python, PyPy3)

접근 서로 연결된 '연결 요소'가 싸이클을 이루는지 아닌지 체크하여 싸이클이 아닌 연결 요소의 개수를 세어주면 된다. 주의할 점은 다른 정점에 연결되지 않은 외딴 정점 또한 트리의 조건에 부합한다는 것이다. 한개의 연결 요소가 싸이클을 이루는지 체크하는 방법으로 BFS 알고리즘을 사용하였다. 첫번째 정점부터 탐색하면서 현재 정점의 visited를 체크하고 False라면 True로 갱신해준다. 첫번째 정점에서 연결된 정점들을 탐색하면서 visited가 False라면 queue에 추가해준다. 탐색을 진행하면서 queue에서 꺼내온 현재 정점의 visited가 True라면 이미 지나온 다른 요소와 다른 방법으로 연결되어 있으므로 (싸이클을 이루므로) tree로 카운트하지 않는다. queue를 모두 탐색했는데 ..

2021. 4. 29. 23:17
반응형