[파이썬] 백준 2644 : 촌수계산

[파이썬] 백준 2644 : 촌수계산 2644번: 촌수계산 (acmicpc.net) 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 실버 2 그래프, BFS, DFS 접근 노드별로 방문처리를 계층적으로 한다. 첫번째 예제에서 7과 3 두 사람의 촌수를 나타내기를 요구했으므로 bfs탐색 시 7을 인수로 주도록 한다. 코드 (bfs) import sys; input = sys.stdin.readline from collections import deque def bfs(node): queue ..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 10.
• textsms

[파이썬] 백준 5567 : 결혼식

[파이썬] 백준 5567 : 결혼식 5567번: 결혼식 (acmicpc.net) 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 실버 2 그래프, BFS, DFS 접근 예제 1을 도식화하면 다음과 같다. 친구의 친구까지만 초대가 되므로 2, 3, 4번 친구까지가 범위에 해당될 것이다. 기존의 bfs방식은 방문한 정점과 그렇지 않은 정점을 1, 0 (또는 True, False)로 구분하기 때문에 친구의 친구와(4번) 친구의 친구의 친구(5번)를 구별할 수가 없다. 따라서 방문한 번호를 다르게 주는..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 9.
• textsms

[파이썬] 백준 4963 : 섬의 개수

[python] 백준 4963 : 섬의 개수 4963번: 섬의 개수 (acmicpc.net) 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 실버 2 그래프, DFS, BFS 접근 좌표를 이동하면서 bfs를 탐색하는 문제를 풀어봤다면 쉽게 풀 수 있는 문제이다. 1은 땅이고 0은 바다이므로, 1을 찾아낼 때 덱에 값을 넣고, 1을 0으로 바꿔 방문처리를 한다. 탐색이 끊기면 사면이 바다인 것이므로 섬의 개수를 카운트하도록 한다. 코드 import sys; input = sys.stdin.readline ..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 9.
• textsms

[파이썬] 백준 11724 : 연결 요소의 개수

[파이썬] 백준 11724 : 연결 요소의 개수 11724번: 연결 요소의 개수 (acmicpc.net) 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 실버 2 그래프, BFS, DFS 접근 방향없는 그래프이므로 간선의 양 끝점을 서로 연결되도록 만든다. bfs탐색을 하다가 큐의 값이 텅텅 비게되면 탐색이 끝나므로 그때 카운트를 해주는 방법으로 연결 요소의 개수를 셈할 수 있다. 코드(BFS) import sys; input = sys.stdin...

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 6.
• textsms

[파이썬] 백준 3184 : 양

[파이썬] 백준 3184 : 양 https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 실버 2 그래프, DFS, BFS 접근 울타리의 경계를 만날 때까지 영역 내의 다른 좌표들을 탐색해야 하므로 bfs가 적합하다. 좌표를 움직이되, 설정한 경계값을 넘지 않았는지, 방문하지 않았는지, 해당 좌표에 울타리가 존재하지 않는지 확인하고 만약 늑대가 있다면 늑대의 수를, 양이 있다면 양의 수를 더해준다. bfs의 탐색이 끝나는 경우는 울타리 내의..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 30.
• textsms

[파이썬] 백준 1260 : DFS와 BFS

[파이썬] 백준 1260 : DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 실버 2 그래프, DFS, BFS DFS, BFS의 구현 방법을 알고 있는 것을 전제로 제시된 문제이다. 다만 정점을 방문은 반드시 오름차순 순서로 이루어져야 하기 때문에, 인접한 정점들을 오름차순으로 정렬한 후에 접근할 수 있도록 구현해야 한다. bfs구현을 할 때는 시간 복잡도가 O(1)인 deque을 이용하는 ..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 27.
• textsms