빵똥

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 1. 접근 문제 속 입력을 그래프로 만들어 위상 정렬하는 문제입니다. 처음에는 input으로 어떻게 그래프를 만들어야 하나 고민이 많았던 문젠데 예제 입력을 그림으로 그려보니 바로 이해가 되서 풀었던 문제입니다. 예제 입력의 두 번째 줄부터 간선 정보라 생각하고 그래프로 그려보면 다음과 같습니다. 입력 받은대로 단방향 그래프를 그리고 자신에게 향하는 간선이 없는 노드를 차례대로..

https://www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 1. 접근 DFS로 접근 시 인접 리스트를 사용하니 O(V + E) == O(500,000 + 499,999) = 1,000,000로 시간 초과 없이 풀 수 있다! 게임의 규칙을 살펴보면 각 말단 노드의 개수 = 말의 수이며 한 턴에 한 번씩 현재 노드의 부모 노드로 이동한다. 또한 게임에서 이기려면 순서가 먼저인 성원이 차례에 마지막 말을 루트로 이동시켜야 한다. 예제 3번을 그림으로 보면 말단..

https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 1. 접근 문제를 풀기 전 시간 복잡도를 구하자! V + E를 T만큼 반복하는데 T는 제시되어 있지 않다! n과 m이 그리 크지 않으니 T도 상식적인 선 안에서 제시되니 일반적인 DFS로 접근해보자! 문제의 조건을 살펴보면 트리의 조건을 제시해주고 해당 조건을 만족하는 개수를 이 형식에 맞춰서 출력해주면 된다. 조건에서 제시된 트리의 기준은 정점이 n이라고 가정했을 때 간선이 n..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 접근 문제를 풀기 전 항상 시간 복잡도를 생각하자! 그래프 탐색에서의 시간 복잡도는 인접 행렬 = V², 인접 리스트 = V + E 이며 이번 문제 포함해 대부분의 문제는 인접 리스트로 접근하니 100,000 + 99,999 = 199,999로 시간 여유는 충분하다! 문제의 조건은 루트를 제외한 각 노드의 부모를 출력하는 것이다. 문제의 예제를 그림으로 그려서 접근해보자. 글로만은 이해가 어려우니 그림을 보며 이해해보자! 탐색을 진행하며 각 정점의 부모가..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 1. 접근 최대 입력값에 따른 시간 복잡도는 다음과 같다. 칸의 갯수 = H * N * M = 1,000,000로 시간제한안에 여유있게 풀 수있다! 문제의 조건을 살펴보자 익은 토마토 기준으로 상,하,위,아래,좌,우 총 여섯 방향으로 토마토는 익어가며 토마토가 비어있는 칸도 있다. 첫 번째 입력 예제를 그림으로 보면 토마토가 잘 익어가다가 비어있는 칸으로 인해 모두 익지 못..

https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 1. 접근 배열의 최대 크기는 50으로 50 * 50칸을 두 번만 방문하면 되니 약 2,500번만에 풀 수 있는 문제다! 문제의 조건을 살펴보자면 땅은 . * X D S로 총 다섯개로 나눌 수 있으며 물과 고슴도치는 매번 위, 오른쪽, 아래, 왼쪽 총 네 방향으로 이동이 가능하며 물은 벽과 비버굴을 통과할 수 없고 비버는 벽과 물 웅덩이를 통과할 수 없다. 다음과 같은 배치가 있다고 가정했을 때 최단 거리는 ..

https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 1. 접근 상근이의 위치, 즉 1번 정점에서의 거리가 2 이하인 정점의 수만 카운트하면 끝이다! 즉, BFS의 시간복잡도인 O(V + E) = 500 + 10000 이면 풀 수 있다! 자신의 친구, 친구의 친구를 정점과 간선에 비유하면 1과 인접한 정점, 1과 인접한 정점과 인접한 정점(??)까지의 수 이며 2번, 3번, 4번 친구가 초대 대상이 된다. 2. 풀이 변수 세팅 stat..

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..