그래프 탐색
-
[Baekjoon Online Judge] 2583번: 영역 구하기문제 풀이/Baekjoon Online Judge 2021. 2. 22. 15:39
2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 요구사항 - 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. - M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그..
-
[Baekjoon Online Judge] 1987번: 알파벳문제 풀이/Baekjoon Online Judge 2021. 2. 21. 12:24
1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 요구사항 - 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. - 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. - 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있..
-
[Baekjoon Online Judge] 2468번: 안전 영역문제 풀이/Baekjoon Online Judge 2021. 1. 20. 20:17
2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 요구사항 - 어떤 지역의 높이를 파악한다. - 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개 만들어 지는 지를 조사한다. - 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다. - 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산한다. - 단, 아무 지역도 물에 잠기지 않을 수도 있다. 높이가 0 이하 일 때 입력 첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 ..
-
[Baekjoon Online Judge] 4963번: 섬의 개수문제 풀이/Baekjoon Online Judge 2021. 1. 19. 17:50
4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 요구사항 - 정사각형으로 이루어진 섬과 바다 지도가 주어진다. - 한 정사각현과 가로, 세로, 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. - 1은 땅이고, 0은 바다이다. - 섬의 개수를 세어 출력한다. 입력 - 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. - w와 h는 50보다 작거나 같은 양의 정수이다. - 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅..
-
[Baekjoon Online Judge] 14502번: 연구소문제 풀이/Baekjoon Online Judge 2021. 1. 19. 17:46
14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 요구사항 - 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. - 연구소는 크기가 N x M인 직사각형으로 나타낼 수 있다. - 연구소는 빈 칸, 벽으로 이루어져 있다. 벽은 칸 하나를 차지한다. - 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우 인접한 빈 칸으로 모두 퍼져나갈 수 있다. - 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. - 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 입력 - 첫째 줄에 지도의 세로 크기 N..
-
[Baekjoon Online Judge] 11724번: 연결 요소의 개수문제 풀이/Baekjoon Online Judge 2021. 1. 18. 19:07
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 요구사항 - 방향이 없는 그래프가 주어진다. - 연결 요소 (Connected Component)의 개수를 구한다. - 연결 요소란? 무향 그래프에서 서로 다른 두 정점이 경로로 연결되어 있으면서 상위 그래프의 추가 정점이 없는 부분 그래프 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝..
-
[Baekjoon Online Judge] 1012번: 유기농 배추문제 풀이/Baekjoon Online Judge 2021. 1. 17. 22:35
1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 요구사항 - 해충 방지에 효과적인 배추흰지렁이를 구입한다. - 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹으며 배추를 보호한다. - 어떤 배추에 배추흰지렁이가 한마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있다. - 한 배추의 상하좌우 네 방향에 다른 배추가 인접한 배추이다. - 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 된다. - 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다. 입력 입력의 첫 줄에는 테..