https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 이분 그래프 설명 https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84 이분 그래프 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 2색변 이분 그래프의 예 그래프 이론에서 이분 그래프(二分graph,..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 난이도 : 실버 1 태그 : 그래프 이론, 깊이 우선 탐색, 너비 우선 탐색, 브루트포스, 그래프 탐색 설명 비가 오는 양에 따라 잠기는 지역이 있을 수도 있고, 없을 수도 있습니다. 높이는 1이상 100 이하 이므로, 1~100 높이 모두를 대상으로 DFS 혹은 BFS를 진행해 안전구역의 최대 개수를 구하면 됩니다 DFS, BFS 중 어느 것을 사용해도 무방하나, 저는 BFS를 사용하여 풀이하였습니다...

https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색 설명 불이 확산되는 와중에 지훈이가 불에 닿지 않으면서 탈출할 수 있는 최소 시간을 출력하는 문제입니다. BFS를 사용해 풀이할 수 있는데, 불과 지훈이의 맵을 따로 두어, 불의 맵을 먼저 BFS 한 후, 지훈이의 맵을 탐색해가며, 각 좌표가 불이 도달하기 이전에 도달할 수 있는지 체크하면 됩니다. 소스코드 i..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A B 보단, B를 역으로 A로 만드는 과정이 더 쉬우며, 오른쪽에 1을 추가하는 연산은 10으로 나눴을때 나머지가 1이면 오른쪽에 1을 추가한 연산으로, 2..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 각각의 점을 정점으로 보고, 인접한 상하좌우의 정점이 서로 연결되어있다고 생각하여, DFS, BFS로 모든 정점에서 탐색을 수행하며 블럭의 개수를 카운트 할 수 있습니다 DFS, BFS중 어느 것을 사용해도 무방하나, 저는 DFS를 사용해 풀이하였습니다. 소스코드 import java.io.BufferedReade..

https://www.acmicpc.net/problem/3182 3182번: 한동이는 공부가 하기 싫어! H-ALGO 회원인 한동이는 공부하는것을 좋아하지 않는다. 하지만 약삭빠르게도 한동이는 공부도 하지 않으면서 어려운 시험을 통과하고 싶어한다. 그러던 와중 어느 날, 한동이의 동기가 한동이에 www.acmicpc.net 난이도 : 실버 3 태그 : 그래프 이론, 그래프 탐색, 브루트포스 알고리즘 설명 이미 물어본 선배를 체크해가며 선배가 가르키는 다른 사람을 계속 따라가서, 이미 물어본 선배일 경우(사이클 발생), 지금까지 몇 명의 선배를 만났는지 저장하고, 가장 큰 수를 출력하면 됩니다. 소스코드 fun main() { val br = System.`in`.bufferedReader() val n..

https://www.acmicpc.net/problem/1388 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net 난이도 : 실버 4 태그 : 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 문제 태그의 그래프 탐색과는 별개로, 그냥 타일의 개수가 몇개인지 다 카운팅해서 풀 수도 있습니다. 소스코드 fun main() { val line = readLine()!!.split(" ") val height = line[0].toInt() val width = line[1].toInt() val..

https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 난이도 : 실버 5 태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 오른쪽과 아래쪽. 두 방향으로만 이동할 수 있고, 해당 칸에 있는 숫자만큼만 이동할 수 있습니다. n의 크기가 매우 작아(2 map[x][y] = st.nextToken().toInt() } } visited[0][0] = true dfs(0, 0) println("Hing")..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 난이도 : 골드 3 태그 : 다이나믹 프로그래밍, 깊이 우선 탐색, 그래프 이론, 그래프 탐색 설명 DFS를 사용해 탐색하는 문제입니다. 다만, M, N이 500 이하의 자연수 이므로 DFS만 사용해서는 시간초과 / 메모리 초과가 발생하며, 다이나믹 프로그래밍 기법이 사용되어야 합니다 dp를 -1로 초기화하여 탐색을 하지 않는 공간을 나타냅니다. DFS를 이용해 탐색하며 이차원 배열 dp에 시작점에서 ..

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 난이도 : 골드5 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색 설명 너비 우선 탐색(BFS, Breadth First Search)을 사용하여 풀이하는 문제입니다. 각 경우의 수를 그래프 형태로 생각하며, 가장 먼저 도달하는 해가 최적의 해인 BFS의 특징을 사용하여 풀이할 수 있습니다. BFS의 '가장 먼저 도달하는 경로가 최적의 경로이다'라는 특징을 잘 모르실 경우, 아래 포스팅을 한번 보고 오시..