채점 현황 (acmicpc.net) 채점 현황 www.acmicpc.net 문제 요약 모든 직원은 정확히 한명의 직속 상사. 트리구조 루트는 민식이 민식이는 자기 직속 부하에게 한번에 한 사람씩 전화를 함 각 부하는 그 밑의 직속에게 한번에 한 사람씩 전화를 검 모든 직원이 뉴스를 들을 때까지 계속됨 전화는 정확히 1분 걸림 모든 직원이 소식을 듣는 데 걸리는 시간의 최솟값을 구하라 민식의 번호는 0, 사원은 1부터 시작 입력 및 제약조건 첫째 줄 : 직원 수 N 1

14890번: 경사로 (acmicpc.net) 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 이번 문제는 처음에 갈피를 못잡아서 시간이 많이 걸렸던 문제다. 문제 아래에 힌트가 있으니 여기서 아이디어를 얻어가면 된다. 그런데, 문제에서 빠진 조건이 하나 있다 바로 가로 세로 경사로를 겹칠 수 있다는 것. 예를 들어 n이 4이고 l이 2인 상황에서 0 3 0 0 2 2 2 3 3 2 2 2 0 2 0 0 위와 같은 경우 세로로 경사로를 놓으면 높이를 표시했을 때 다음과 같다. 0 0 0 0 0 2 0 0 0 1 0 0 0 0 0 0 ..

14888번: 연산자 끼워넣기 (acmicpc.net) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 자체는 평범한 난이도의 문제다. permutation을 이용해 각 연산자의 배치 방법을 전부 시도해보면 된다. 그런데 이 문제를 풀면서 깨달은 점 한가지가 있어서 포스팅을 해본다. 이 문제는 사실 예전에 한 번 풀어봤었던 문제인데 이번에 새로 푸니까 시간이 세배 이상 오래 걸리기에 무슨 이유에서인지 하나씩 시도해봤는데 결과는 permutations를..

14502번: 연구소 (acmicpc.net) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 처음 봤을 때는 상당히 당황스러운 문제였다. 어느 부분에 벽을 놓아야 할지 감이 잘 안왔던 문제였는데 문제에서 한가지 힌트를 얻었다. 안전 영역의 크기를 구하는데 최댓값을 구하라는 걸 보니 여러 번 시도하는 문제라는 것을 알 수 있었다. 그렇다면 가장 쉬운 방법으로 BFS를 Backtracking하여 푸는 문제로 생각이 들었다. 그러면 시간복잡도는 어떻게 될까? 연구소의 크기가 최대 8*8이고 여기서 벽을 3개 세워야 하므로 64..

13460번: 구슬 탈출 2 (acmicpc.net) 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 2차원 배열 백트래킹 문제. 여기서 포인트는, 구슬이 한번에 두개가 동시에 움직인다는 것이다. 즉, 구슬을 기준으로 BFS로 이동시키면, 먼저 이동하는 구슬이 있으므로 구현할 수 없다. 따라서 판의 기울임을 기준으로 움직여주어야 한다. 이를 구현하려면 일단 판을 왼쪽으로 기울이는 swiping 함수가 필요하고 한쪽으로 기울이는 함수를 네 방향으로 적용하기 위해 ..

16985번: Maaaaaaaaaze (acmicpc.net) 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 3차원 배열을 이용한 문제다. 문제를 보면 바로 감이 오는데, backtracking과 bfs를 동시에 사용하는 문제다. 5*5 판을 회전하고 쌓는 부분은 backtracking으로, 경로 탐색은 bfs로 구현하면 된다. 먼저 90도를 돌려야 하는데 매번마다 돌리면 같은 배열을 계속해서 만들게 되므로 한번에 전부 돌려놓은 배열을 만들었다. 먼저 src를 전부 입력받은 후, 같은 크..