https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 난이도 : 골드 4 태그 : 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 얼음을 녹이면서 덩어리가 두개가 되는 시점을 찾는 문제입니다. 얼음을 녹이는 구현 부분에 약간의 시뮬레이션 요소가 들어갔다고 볼 수 있을 것 같네요. 얼음이 몇 덩어리인지 확인하는 부분은 DFS / BFS 를 사용할 수 있을 것 같은데, 저는 DFS를 사용해 풀이하였습니다. 접근 방법 1...

https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 난이도 : 골드 5 태그 : 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색 설명 같은 육지 내에서 최단 경로로 이동했을 때, 거리가 가장 긴 경로를 찾는 문제입니다. BFS를 응용하여 풀 수 있을 것 같은데요. 그럼, 같은 육지 내 겨올가 최대가 되는 경우는 어떻게 찾을 수 있을까요? 단순히 육지의 모든 점에서 BFS를 수행하면 됩니다. 가로, 세로의 크기가 최대 50밖에 되지 않..

https://www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 줄에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프 이론, 자료 구조, 그래프 탐색, 분리 집합, 플로이드–워셜 설명 다소 복잡한 문제라, 지문을 두 세번 정도 정독했던 것 같네요. 서로 알고 있는 사람들의 관계가 주어질 때, 서로 알고 있을 경우 무조건 같은 위원회지만, 위원회는 최대한 많아야 하므로, 서로 알고 있지 않을 경우 무조건 다른 위원회로 분리합니다. 위의 말은 최댓값이... 최소가 된다...?는 ..

https://www.acmicpc.net/problem/17142 난이도 : 골드 3 태그 : 그래프 이론, 브루트 포스, 그래프 탐색, 너비 우선 탐색 설명 연구소 시리즈 3번째 문제입니다. 해당 문제는 크게 1. 입력 2. 바이러스 m개를 고르는 조합 (DFS를 사용한 브루트포스) 3. 바이러스 퍼뜨리기 (BFS) 으로 나눌 수 있겠습니다. 입력값을 받을 때, 바이러스의 위치를 저장 및 빈 공간을 카운트 한 뒤, 이를 DFS을 사용해 바이러스를 m개 고르고, bfs로 바이러스를 퍼뜨립니다. 소스코드 값 입력 import java.util.* import kotlin.collections.ArrayList data class Virus(val x: Int, val y: Int) lateinit var..

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 난이도 : 골드 3 태그 : 구현, 그래프 이론, 그래프 탐색, 너비우선탐색, 시뮬레이션, 깊이우선탐색 설명 삼성 기출 문제로 유명한 마법사 상어 시리즈 중 '마법사 상어와 파이어스톰' 문제입니다. 시뮬레이션 문제로써, 1. 파이어스톰을 n번 시전 2. 모든 파이어스톰 시전 후 가장 큰 덩어리 찾기 크게 두 파트로 나눌 수 있습니다. 파이어스톰 시전 과정은 단순 구현이지만 모든..

https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 정렬, 깊이 우선 탐색 설명 이름 처럼 깊이 우선 탐색 (DFS, Depth First Search)의 연습문제 입니다. 그래프를 탐색하는데는 여러 방법이 있습니다. 그 중 꽤 유명한 탐색방법인 DFS를 연습해봅시다. DFS는 트리 or 그래프에서 최대한 깊이 탐색한 ..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프 이론, 그리디 알고리즘, 그래프 탐색, 깊이 우선 탐색 설명 첫째 열에서 시작해 서로 교차하거나 중첩되지 않으면서 마지막 열로 가는 경로를 찾는 문제입니다. 1번 예제 같은 경우는 최대 두 가지 경로를 그릴 수 있습니다. 2번 예제 같은 경우는 아래와 같이 최대 5개의 경로(파이프 라인)이 있습니다. 파이프라인은 왼쪽에서 오른쪽 방향으로 놓을 수 있으며, 오른쪽 대각선 위, 오..

https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프 이론, 최소 스패닝 트리 설명 최소 스패닝 트리를 응용하여 각 간선의 최소값을 구하면서, 최대 스패닝 트리를 구해 각 간선의 최댓값을 구하는 문제입니다. 최대 스패닝 트리의 경우, 최소 스패닝 트리에서 단순히 정렬 조건만 반대로 지정하여 한 번 더 수행하면 구할 수 있습니다. 최소 스패닝 트리를 잘 모르신다면 아래 포스팅을 참..

https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 난이도 : 골드 2 태그 : 그래프이론, 그래프탐색, 깊이 우선 탐색, 트리 설명 해당 문제 같은 경우는 DFS + Inorder(중위순회) 를 통해 구현할 수 있겠습니다. 위와 같은 노드가 있다고 가정해봤을때, 이를 인오더로 탐색하면 어떻게 될까요? 7-4-8-2-1-5-3-6-9 순으로 방문을 하게 됩니다. 즉, 좌-부모-우 순으로 탐색을 하기 때문에 좌측에 노드가 있을 경우..

https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 난이도 : 골드 4 태그 : 자료구조, 그래프 이론, 분리집합, 트리 설명 각 뉴런은 시냅스로 연결됩니다. 뉴런은 노드(Node) 혹은 정점(Vertex), 시냅스는 간선(Edge)로 볼 수 있겠습니다. 모든 뉴런이 시냅스로 연결되면서 사이클이 없어야 하는 트리(사이클이 없는 연결 그래프) 구조여야 합니다. 사이클이 생기지 않으면서, 각 노드를 간선으로 병합하는 과정에서는 분리집합 - 유니온파인..