문제 풀이/백준 알고리즘

[baekjoon 16437] 양 구출 작전 (DFS, 트리) (C++)

https://www.acmicpc.net/problem/16437 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net 각 섬에 있는 양들을 1번 섬으로 옮겨야 한다. 하지만 경로 상에 늑대가 있다면 양은 늑대의 수만큼 줄어든다. 각 섬에서 1번 섬으로 가는 루트는 유일하므로 트리 구조를 생각할 수 있고, 늑대는 양을 최대 1마리만 잡아먹으므로 섬에 계속 남아서 오는 양을 잡아먹는 것이 아닌, 한 마리 잡아먹으면 늑대 역시 줄여줘야 한다. 처음엔 DFS로 모든 양의 위치에서 루트까지 탐색을 해주었..

[baekjoon 2623] 음악프로그램 (위상정렬) (C++)

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 입력값을 인접 그래프로 바꾼 뒤, 위상 정렬을 하면 되는 문제이다. 위상 순서가 여러 줄에 나눠서 주어지지만, 1 2 3을 1-2, 2-3으로 나눠서 생각해서 정리하면 된다. (가수들끼리의 순서만 유지해서 정리하면 되므로) 또한, 정렬할 수 없을 때 0을 출력해야 하는 조건만 잘 구현해주면 쉽게 풀릴 것이다. #include #include #include using names..

[baekjoon 2239] 스도쿠 (완전탐색, 백트래킹) (C++)

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 말 그대로 9X9의 스도쿠 판의 빈칸을 채우는 문제이다. 처음에는 이걸 어떻게 알고 풀지?라는 생각이 들었는데 9x9의 작은 사이즈로, N-Queen문제처럼 완전 탐색으로 다 돌려보면 되겠다고 생각이 들었다. 스도쿠의 규칙으로는 세로줄, 가로줄, 9개의 작은 사각형 중 하나에 1~9까지 채워야 하고, 중복된 숫자가 있으면 안 된다. 따라서 해당 범위에 맞게 체크 함수 3개를 만들어줬고, 빈칸..

[baekjoon 1516] 게임 개발 (위상정렬, DP) (C++)

https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 입력으로 각 건물을 짓는데 걸리는 시간과, 이 건물을 짓기 위해서 선행되어야 하는 건물의 번호가 주어진다. 즉, 건물을 짓는 순서를 그래프로 나타내면 DAG(Directed Acyclic Graph) - 사이클을 갖지 않는 단방향 그래프가 되고, 이를 통해 노드 간 고유 순서를 위배하지 않으면서 정렬하는 위상 정렬을 이용할 수 있다. 위상 정렬의 방법은 1. 스택을 이용하는 방법과 2...

[baekjoon 1339] 단어 수학 (브루트포스, 그리디) (C++)

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 알파벳 대문자로 이루어진 단어에 0~9까지 숫자를 대입해서 그 결과가 가장 큰 숫자를 찾는 문제이다. 예를 들어 ABC + AAA이면 A에 9, B에 8, C에 7을 대입하면 987+999 = 1986이 결과가 되는 것이다. 즉, 알파벳 대문자가 나온 빈도수와 자릿수에 맞춰서 가장 큰 9부터 가장 작은 0을 어떻게 대입해야 할지를 정해줘야 한다. 방법으로는 1. 완전 탐색으로 모든 조합으로 ..

[baekjoon 16928] 뱀과 사다리 게임 (BFS) (C++)

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 최소한의 주사위를 굴려서 100까지 가야 하고, 가는 도중에 사다리와 뱀이 있다. 사다리에 해당하면 도착점(100)에 가까워지고, 뱀을 만나면 시작점(1)과 가까워진다. 1. 한 칸에 뱀과 사다리가 이중으로 나오는 경우가 없다고 했으니 1차원 배열에 뱀과 사다리를 모두 입력받았고, 2. 주사위를 통해 (1~6)까지의 이동을 할 수 있으므로 BFS를 하..