https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프 이론, 최소 스패닝 트리 설명 모든 별을 선으로 이어 별자리를 만드는 문제입니다. 별자리를 잇는다는 건, 두 별을 직선으로 이은 것이며, 모든 별자리는 직/간접적으로 서로 이어져 있어야 합니다. 별을 이을 때 거리만큼의 비용이 들 때, 모든 별을 직/간접적으로 이으면서 그 비용이 최소가 되는 경우를 찾아야 합니다. "모든 별(노드)를 선으로 직/간접적으로 이으면서..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 난이도 : 골드 4 태그 : 그래프 이론, 그래프 탐색, 데이크스트라, 0-1 너비 우선 탐색 설명 시작점 (0,0)에서 도착점 (n,m)으로 가려면 얼마나 많은 벽을 부셔야 하는지 구하는 문제입니다. 특이하게도 시작점에서 도착점으로 가는 비용이나 거리가 아닌, 얼마나 많은 벽을 부셔야 하는가를 구하는 문제입니다만, 최단 경로 하면 떠오르는 BFS, 다익스트라를 응용하여 풀 ..

https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 난이도 : 골드 2 태그 : 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색 설명 삼성 기출문제로도 유명한 상어 시리즈 중 상어 중학교 입니다. 다른 상어 시리즈와 마찬가지로 시뮬레이션 + 그래프(탐색 및 백트래킹) + 배열 뒤집기가 인상적이였던 문제였습니다. 계속 테스트케이스가 다르게 나왔는데, 시뮬레이션 문제 특성 상 한 회차당 맵이 어떻게 바뀌는지 확인해야 하기 때문에 엑..

https://www.acmicpc.net/problem/16920 16920번: 확장 게임 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프 탐색, 그래프 이론, 너비 우선 탐색 설명 각 플레이어 i는 한 턴에 S(i) 거리 만큼 확장을 할 수 있습니다. 각 플레이어 별로, 그리고 한 싸이클씩 그래프 탐색을 진행하는게 포인트라 할 수 있습니다. 예제중 하나를 가져와봤습니다. 초기 상태가 아래와 같고, 플레이어 1이 2칸, 플레이어 2가 1칸씩 움직일 수 있는 경우입니다. 1..1 .... .... ..

https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 난이도 : 골드 2 태그 : 구현, 그래프 이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색 설명 3차원 큐브를 탈출하는 문제입니다. 한 층씩 좌우로 층을 회전할 수 있고, 한 층씩 마음대로 쌓을 수 있기 때문에, 각 층을 회전하여 만들 수 있는 모든 경우의 수를 탐색하는 완전탐색(DFS) 1번, 각 층을 쌓아 만들 수 있는 모든 경우의 수를 탐색하는 완전탐색(DFS..

그래프 탐색 정점(Node, Vertex)과 간선(Edge)로 이루어진 그래프. 이 그래프를 탐색하는 방법에는 대표적으로 두 가지 방법이 있습니다. 깊이 우선 탐색(DFS, Depth-First Search)와 너비 우선 탐색(BFS, Breadth-First Search) 입니다. 물론 다른 그래프 탐색 알고리즘도 존재하나, 이 둘이 가장 유명한 방법이지 않을까 싶네요. 깊이 우선 탐색 (DFS, Depth - First Search) DFS는 깊이 우선이라는 이름처럼 깊이를 우선적으로 탐색합니다. 한 노드의 연결된 노드를 먼저 탐색한다는 의미죠. 해당 그래프를 DFS로 탐색한다면 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 순서로 탐색합니다. 한 노드를 탐색할 때, 해당 노드와 연결된 ..

https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프탐색, 그래프이론, 너비우선탐색 설명 한 좌표에 다른 좌표의 불을 켤 수 있는 스위치가 있습니다. 복수개일 수 있으며, 스위치를 총 몇 개나 작동시킬 수 있는지(불을 킬 수 있는지)를 구하는 문제입니다. BFS를 사용하면 될 것 같지만, 스위치를 켜서 갈 수 있는 좌표가 늘어남에 따라, 해당 좌표와 인접한 좌표..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 난이도 : 실버 1 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색 설명 특정 위치로 이동할 수 있는 가장 적은 횟수를 찾는 문제입니다. bfs를 활용할 수 있겠는데요. 단순히 4방향 bfs가 아닌 나이트의 이동에 맞춘 8방향 bfs를 사용하면 될 것 같습니다. 나이트의 이동은 상,하,좌,우 중 2칸 이동하고, 수직방향으로 1칸 혹은 상하좌우 1칸 이동 후 이동방향의 대각선 방향 1칸 이동으로..

https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프 이론, 그래프 탐색, 너비 우선 탐색 설명 몇 개의 역이 튜브로 연결되어 있고, 1번에서 N번까지 가는데 거쳐야 하는 최소 역 개수를 찾는 문제입니다. 시도 1 음... 각 튜브들끼리 연결되있다고 하니까, 단순히 각 튜브들끼리 모든 순서쌍을 그래프를 만들면 풀리지 않을까요? (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)..

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 난이도 : 골드 5 태그 : 그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색 설명 가중치가 있는 그래프(트리)에서, 두 노드간 거리를 구하는 문제입니다. DFS/BFS를 사용해 그래프(트리)를 탐색하여 풀 수 있을 것 같은데요. 저는 BFS를 사용해 풀이하였습니다. 소스코드 데이터용 클래스 Node Node는 to (목표 노드), cost(목표 노드로 가는..