빵똥

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 1. 접근 먼저 최대값과 시간 복잡도를 구해보자면 모든 관계를 다 둘러보아도 5,000번이면 되니 최대값은 넉넉하고 시간 복잡도로는 유저(간선)마다 각각의 케빈 베이컨 수를 구해야 하니 (유저 수 + 관계) * 유저수 = 100,000로 시간 또한 넉넉하다. 문제의 설명을 그래프와 표로 정리하자면 다음과 같다. 표와 같이 각 유저의 케빈 베이컨의 수..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 접근 N과 K모두 최대 10만에 있을 수 있고 방문횟수 또한 끝에서 끝 지점으로 -1로만 이동했을 경우 10만번 방문한다. 즉 시간복잡도 및 최대값은 10만으로 BFS로 접근 가능하다. BFS 문제이지만 노골적으로 격자판이나 그래프가 주어지지 않기 때문에 수빈이의 위치와 동생의 위치까지를 각 정점으로 볼 수 있고 이동 가능한 경로는 그림과 같이 x - 1, x + ..

https://www.acmicpc.net/problem/18404 18404번: 현명한 나이트 첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. ( www.acmicpc.net 1. 접근 나이트가 갈 수 있는 곳을 확인하는 게 500²에 M의 위치를 확인하여 출력하는 게 1000으로 BFS를 이용하여 시간 내에 충분히 풀 수 있는 문제이다. 먼저 나이트의 이동경로를 사용하기 편하게 배열로 저장하고 static int[][] dir = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1..

BFS 기초 문제 중 하나이다. 1. 접근 정점의 최대 갯수는개수는 100개이며 완전 그래프라 가정해도 간선의 개수는 n * (n - 1) / 2 = 100 * (100 - 1) / 2 = 4,950개, 그에 따른 무방향 그래프의 차수의 개수는 4,950 * 2 = 9,900개로 시간제한에 여유 있게 풀 수 있다. 2. 풀이 두 번째 입력값인 두 사람의 촌수, 즉 예제로 보자면 다음 그림과 같다. 다른 기초 BFS 문제와 같이 이동할 때 마다 배열에 1씩 누적하며 최종 목적지의 값을 출력하면 끝이다. 전역 변수 및 input static int V, E, start, end; static ArrayList[] graph; static int[] dist; public static void main(Str..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 2178번과 같이 너비 탐색 기초 문제다. 1. 접근 테스트 케이스의 최대치가 나와있지는 않으나 체스판의 최대 크기인 300² 를 모두 밟아도 90,000으로 시간제한 걱정 없이 풀이에 접근하면 된다. 그림 예제에 나와있듯 나이트의 이동 경로를 미리 배열로 짜둔다면 다음과 같다. (시계방향) static int[][] dir = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, ..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 가중치 없는 그래프에서 최단 거리를 구하는 가장 기초적인 BFS 문제다. 1. 접근 미로의 모든 칸을 다 밟는다고 가정해도 최대 N * M, 즉 100²인 10,000으로 시간제한 1초 내에 풀 수 있다. 이동할 때의 조건으로는 다음과 같으며 배열로 미리 저장해두면 다음과 같으며 static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; 좌표상 (n - 1)(m - 1)에 도착했을 때 ..

DFS와 BFS를 동시에 활용해야 하는 문제인 백준 14502-연구소 문제를 풀어보자. (solved.ac 티어 = 골드 5) https://www.acmicpc.net/problem/14502 1. 접근 문제에서 확인할 수 있듯 그래프의 크기는 8 * 8 = 64가지이며 바이러스의 확산을 막는 벽을 반드시 3개를 설치해야 한다. 즉 우리가 해야 할 일은 벽을 3개 세워본다 -> 바이러스를 퍼트린다(0인 곳) -> 남아있는 안전지역을 확인한다 -> 최 갯값을 갱신한다. 이렇게 네 가지로 정리할 수 있으며 최댓값인 64개의 공간에 중복되지 않게 벽을 3개 세워본다 = n! / ((n - m)! * m!) = 41664 벽을 세운 후 하나하나 탐색하며 안전지대인지 확인한다 = N² = 64 시간 복잡도 = ..