본문 바로가기

전체보기192

[4963번] 섬의 개수 - Python 문제 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 import sys input = sys.stdin.readline from collections import deque # 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있음 dx = [-1, 0, -1, +1, +1, 0, +1, -1] dy = [-1, -1, +1, 0, +1, +1, -1, 0] def bfs(i, j): queue.append((i, j)) visited[i][j] = 1 while que.. 2024. 3. 19.
[백준 11725번] 트리의 부모 찾기 🤯 문제 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 예제 입력 1에 대한 트리 1 / \ 6 4 / / \ 3 7 2 / 5 BFS import sys input = sys.stdin.readline from collections import deque # 노드의 개수 N (2 ≤ N ≤ 100,000) N = int(input().rstrip()) tree = [[] for _ in range(N+1)] for i in range(1, N): a, b = map(int, input().split()) tree[a].append(b) tree[b].append(a) .. 2024. 3. 15.
[백준 2468번] 안전 영역 - Python 문제 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 from collections import deque import sys input = sys.stdin.readline N = int(input()) max_rain = 0 graph = [] for _ in range(N): row = list(map(int, input().split())) graph.append(row) max_row = max(row) max_rain = max(max_rain, max_row) now_rain = 1 max_safe.. 2024. 3. 14.
[백준 2589번] 보물섬 - PyPy3 문제 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 예전에 푼 문제인데 오랜만에 다시 푸니 이틀 정도 애먹었다.. python으로 제출시 시간 초과가 나서 PyPy3로 제출. 풀이 # 2589번 보물섬 # 육지 L, 바다 W # 상하좌우 육지 이동 가능, 한 칸 이동시 한 시간 # 보물 -> 서로 간에 최단 거리로 이동(BFS)하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있음. # -> 끝에서 끝으로 이동시 서로 가장 긴 시간이 걸리는 육지에서 최단거리를 구해라! (완전 탐색) # 보물이 묻혀 .. 2024. 3. 14.
[백준 11724번] 연결 요소의 개수 - Python, DFS/BFS 문제 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 정점(N)과 간선(M)의 개수가 주어질 때 연결 요소의 개수를 구하라. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 간선 u, v (1 ≤ u, v ≤ N, u ≠ v) 대표적인 DFS/BFS 문제이다. 시간 제한 3초, 메모리 제한 512 MB에 주의해야 한다. 풀이 ✏️ DFS import sys input = sys.stdin.readline sys.setrecursion.. 2024. 3. 12.
[백준 2667번] 단지번호붙이기 - Python 문제 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 # 1 - 집이 있는 곳, 0 - 집이 없는 곳 # 단지 수 출력, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력해라. import sys input = sys.stdin.readline # 정사각형 지도 크기 n = int(input()) square_map = [] for i in range(n): square_map.append(list(map(int, input().rstrip()))) cnt = 0 result = 0 def dfs(x.. 2024. 3. 9.

티스토리툴바