https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 난이도 : 골드 3 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 비트마스킹 접근법 DFS / BFS를 이용한 그룹화 문제입니다. 특이한 점은 0 ~ 15 범위 내 숫자가 주어져 벽의 위치를 알려준다는 점인데요. 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어집니다. 예를 들어 (0, 0)의 경우..

https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 맨 위에서 맨 아래까지 도달할 수 있는지 판단하는 문제입니다. dfs / bfs를 응용하여 풀 수 있는데요. 맨 위의 모든 점에서 dfs / bfs를 시작하여 최하층에 도달할 수 있다면 성공입니다. 좌측부터 1번째 통로를 탐색한 결과, 벽에 막혀 가지 못합니다. 2번..

https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 난이도 : 실버 1 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 울타리로 분리된 각 구역에 양과 늑대가 있습니다. 양이 더 많다면 늑대를 쫒아낼 수 있고 늑대가 더 많거나 양과 수가 동일하다면 늑대가 양을 다 먹어버립니다. DFS, BFS를 사용한 그룹화 기법을 응용하는 문제입니다. 접근방법 1. 한 점을 대상으로 방문하지 않은 점이라면 해당 점을 DF..

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 난이도 : 골드 4 태그 : 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색 설명 뿌요뿌요 게임 시뮬레이션입니다. 연결된 뿌요의 개수가 4개 이상일 경우 뿌요가 삭제되고, 중력의 영향으로 밑으로 내려온 뒤 4개 이상의 뿌요가 새롭게 생기면 연쇄적으로 해당 뿌요 역시 제거됩니다. 뿌요의 상태가 주어졌을 때, 총 몇 번이나 연쇄적으로 뿌요가 삭제되는지 구하는 ..

https://www.acmicpc.net/problem/4993 4993번: Red and Black There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles. Wr www.acmicpc.net 난이도 : 실버 1 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 설명 전형적인 DFS/BFS로..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 난이도 : 골드 4 태그 : 수학, 그래프이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 조합론, 깊이 우선 탐색 설명 위와 같이, 하나의 시를 2개의 선거구로 나누려 합니다. 선거구의 각 구역은 모두 직/간접적으로 이어져 있어야 하며,이때 두 선거구 간의 인원 수의 차이가 최소가 되어야 합니다. n이 2 !selected[index] }.sum() // 선거구2 인구 수 answer = minOf(ans..

https://www.acmicpc.net/problem/24484 24484번: 알고리즘 수업 - 깊이 우선 탐색 6 정점 1번에서 정점 4번을 방문한다. 정점 4번에서 정점 3번을 방문한다. 정점 3번에서 정점 2번을 방문한다. 정점 5번은 정점 1번에서 방문할 수 없다. 따라서, ti 값은 1번 정점부터 1, 4, 3, 2, 0이다 www.acmicpc.net 난이도 : 실버 2 태그 : 깊이 우선 탐색, 정렬, 그래프 탐색, 그래프 이론 설명 깊이 우선 탐색 1-2번 + 3-4번을 합친 형태면서, 깊이 우선 탐색 5번의 내림차순 방문 버전입니다. 1~5번을 푸신 분들이라면 별로 어렵지 않게 푸실 수 있을 문제입니다. 1번 노드 2번 노드 3번 노드 4번 노드 5번 노드 6번 노드 순서 1 4 2 ..

https://www.acmicpc.net/problem/24483 24483번: 알고리즘 수업 - 깊이 우선 탐색 5 정점 1번에서 정점 2번을 방문한다. 정점 2번에서 정점 3번을 방문한다. 정점 3번에서 정점 4번을 방문한다. 정점 5번은 정점 1번에서 방문할 수 없다. 따라서, ti 값은 1번 정점부터 1, 2, 3, 4, 0이다 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 정렬, 깊이 우선 탐색 설명 깊이 우선 탐색 1번 + 3번이라고 볼 수 있습니다. 방문 순서를 체크하는 1번과 깊이를 체크하는 3번을 잘 풀었다면 쉽게 푸실 수 있을 겁니다. 개념 자체는 1-2번, 3-4번과 동일합니다. 오름차순으로 방문할 경우, 방문 순서는 1 -> 2 -> 4 ->..

https://www.acmicpc.net/problem/24482 24482번: 알고리즘 수업 - 깊이 우선 탐색 4 깊이 우선 탐색 트리는 1, 2, 3, 4번 노드로 구성된다. 1번 노드가 루트이다. 1번 노드의 자식은 4번 노드이다. 4번 노드의 자식은 3번 노드이다. 3번 노드의 자식은 2번 노드이다. 5번 노드는 1번 노드 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 정렬, 깊이 우선 탐색 설명 트리의 경우, 탐색의 방문 순서에 관계없이 동일한 깊이를 가지겠지만, 문제에서 주어지는 그래프는 사이클이 있을 수 있는 그래프이기 때문에, 깊이 우선 탐색으로 탐색할 경우 탐색 순서(번호가 작은 노드부터 / 번호가 큰 노드부터)에 따라 각 노드의 깊이가 달라질 ..

https://www.acmicpc.net/problem/24481 24481번: 알고리즘 수업 - 깊이 우선 탐색 3 깊이 우선 탐색 트리는 1, 2, 3, 4번 노드로 구성된다. 1번 노드가 루트이다. 1번 노드의 자식은 2번 노드이다. 2번 노드의 자식은 3번 노드이다. 3번 노드의 자식은 4번 노드이다. 5번 노드는 1번 노드 www.acmicpc.net 난이도 : 실버 2 태그 : 그래프 이론, 그래프 탐색, 정렬, 깊이 우선 탐색 설명 깊이우선탐색 1, 2번이 몇 번째로 방문했는지를 출력하는 것이라면, 깊이우선탐색 3, 4번은 깊이(depth)를 출력하는 문제입니다. 트리의 경우, 탐색 순서가 어떻든간에 각 노드의 깊이는 모두 동일하겠지만, 해당 문제는 사이클이 존재할 수 있는 그래프에서의 D..