목록Computer Science (228)
DHistory
문제 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 import sys from collections import deque n = int(sys.stdin.readline().rstrip()) maps = [] for _ in range(n): maps.append(list(map(int, sys.stdin.readline().rstrip()))) visited = [[False for _ in range(n)] for _ in range(n)] dx = [-1, 0, 1, 0] dy = [0, -1,..
문제 25516번: 거리가 k이하인 트리 노드에서 사과 수확하기 n개의 정점과 n - 1개의 간선으로 구성된 트리 T가 있다. 정점 번호는 0부터 n - 1까지이고 0번 정점이 루트이다. 모든 간선의 길이는 1이다. 트리 T의 각 정점에는 사과가 0개 또는 1개 놓여있다. 루 www.acmicpc.net 풀이 """ n개의 정점 / n - 1개의 간선 번호는 0부터 n - 1까지 0번 정점이 루트 / 모든 간선의 길이는 1 각 정점에는 사과가 0개 또는 1개 놓여있다. 루트 노드에서 거리가 k이하인 노드에 있는 사과를 수확하려고 한다. 수확할 수 있는 사과 개수를 출력하자. 0(1) - 1 - 3(1) ㄴ 4 ㄴ 2 - 5(1) ㄴ 6 - 7(1) 0, 3, 5 => 2개 """ import sys fr..
문제 18126번: 너구리 구구 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이 www.acmicpc.net 풀이 """ 입구 1 / 각 방마다 번호가 새겨짐 입구에서 최대한 먼 방에 아이스크림을 숨긴다. 1 - 2 (3) ㄴ 3 (2) ㄴ 4 (4) 1 - 2 - 4 (7) """ import sys from collections import deque n = int(sys.stdin.readline().rstrip()) nodes = [[] for _ in range(n + 1)] visited = [False] * (n + 1) for _ in r..
문제 21938번: 영상처리 화면의 세로 $N$, 가로 $M$ 값이 공백으로 구분되어 주어진다. 두 번째 줄부터 $N + 1$줄까지 $i$번째 가로를 구성하고 있는 픽셀의 $R_{i,j}$, $G_{i,j}$, $B_{i,j}$의 값이 공백으로 구분되어 총 $M$개 주어진 www.acmicpc.net 풀이 """ 세로의 길이 N 가로의 길이 M RGB 색상의 이미를 담고 있다. - 모든 픽셀에서 "세 가지 색상"을 "평균"내어 경게값 T보다 "크거나 같으면" 255, "작으면" 0으로 바꾼다. - "255인 픽셀은 물체로 인식"한다. - 값이 255인 픽셀들이 "상하좌우로 인접"해있다면 이 픽셀들은 "같은 물체로 인식" 물체가 총 몇 개 있는지 구하는 프로그램을 작성하시오. """ import sys f..
문제 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 풀이 """ 검은색 -> 전류 차단 (1) 흰색 -> 전류 통함 (0) 위쪽에서 전류 공급 상하좌우로 전달 아래쪽까지 전류가 공급될 수 있는지 판단하는 프로그램 """ import sys from collections import deque n, m = map(int, sys.stdin.readline().rstrip().split()) maps = [] for _ in range(n): maps.append(list(ma..
문제 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 풀이 """ 할아버지 - 아버지 - 나 ㄴ 1촌 ㄱㄴ 1촌 ㄱ ㄴ 2촌 ㄱ 두 사람의 촌수를 계산하는 프로그램 9 (전체 사람의 수) 7 3 (촌수를 계산해야 하는 서로 다른 두 사람의 번호) 7 (부모 자식들 간의 관계의 수) 1 2 1 3 2 7 2 8 2 9 4 5 4 6 1 - 2 - 7 ㄴ 8 ㄴ 9 ㄴ 3 4 - 5 ㄴ 6 친척 관계가 없는 경우 -1 """ import sys from collections import deq..
문제 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 """ 1: [4, 6] 2: [4] 3: [5, 6] 4: [1, 2, 7] 5: [3] 6: [1, 3] 1 - 6 - 3 - 5 ㄴ 4 - 2 ㄴ 7 4 6 1 3 1 4 BFS 현재 노드가 부모 노드가 된다. """ import sys from collections import deque n = int(sys.stdin.readline().rstrip()) nodes = [[] for _ in range(n + 1)] for _ in range(n - 1): a, b = map(int, sys.stdin.re..
문제 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 import sys from collections import deque dx = [-1, -1, -1, 0, 1, 1, 1, 0] dy = [1, 0, -1, -1, -1, 0, 1, 1] def solution(graphs, x, y, visited, n, m): if visited[x][y] or not graphs[x][y]: return False queue = deque([(x, y)]) visited[x][y] = True while..
문제 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 풀이 import sys from collections import deque n, m = map(int, sys.stdin.readline().rstrip().split()) visited = [False] * (n + 1) graphs = [[] for _ in range(n + 1)] for _ in range(m): a, b = map(int, sys.stdin.readline().rst..
문제 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 import sys from collections import deque t = int(sys.stdin.readline().rstrip()) dx = [-1, 0, 1, 0] dy = [0, -1, 0, 1] def solution(graph, x, y, n, m): if graph[x][y] in [0, -1]: return False queue = deque([(x, y)]) graph[x][y] = -1 while queue: x, y = queue.pop..