[파이썬] 백준 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

[파이썬] 백준 2210 : 숫자판 점프

[파이썬] 백준 2210 : 숫자판 점프 https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 실버 2 그래프, DFS, 브루트포스 접근 방문처리를 할 필요가 없으므로 브루트포스와 같은 접근을 해야 한다. 모든 좌표에 대한 DFS를 진행하고, 글자 수를 하나씩 채우다가 길이가 6이 되는 경우 그 문자열이 기존에 추가했던 적이 있는지 없는지를 확인하고 리스트에 추가한다. 마지막으로 해당 리스트의 길이를 출력한..

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