https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 로봇 청소기가 움직이면서 더러운 칸을 모두 제거하기 위한 최단 거리를 구하는 문제입니다. 로봇 청소기 시작 위치를 포함하여 더러운 곳의 위치를 노드로 잡고 bfs를 이용하여 각 노드 사이의 최단 거리를 구한 뒤 로봇 청소기 시작 위치를 시작으로 dfs를 돌려 전체 합의 최단 거리를 구하였습니다. (외판원 문제랑 비슷한 느낌으로 dp 추가하면 더 빨리 할 수 있을 것 같다...!!) bfs 과정에서 각 노드..
https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 거울을 설치하여 문 2개를 이을 때 최소 거울 개수를 구하는 문제입니다. 처음에 거울 설치 가능 위치에 따라 해당 경로의 방문 여부를 따로 판단하기에는 (bfs 돌면서 visited 배열 초기화 후 재계산 or 큐에 visited 배열 넣기) 너무 사이즈가 클 거 같아서 우선순위 큐를 이용해 풀어보려했습니다. 하지만 반례가 있었기에 (거울 위치가 계속 돌 수 있음, 그럼 결국 visi..
https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 뭔가 dp를 적용하면 될 거 같은 문제였지만 아이디어를 생각해내는데 좀 시간이 걸렸습니다. (뭔가 비슷한 문제 전에 푼 거 같기도..??) 자식 노드 1명에게만 전화할 수 있으므로, 각 자식 노드가 자식 노드가 루트인 서브트리로 전파하는데 걸리는 시간을 알고있다고 가정하면, 그 결과의 내림차순으로 1씩 더해준 결과의 최댓값이 결국 해당 노드가 루트인 서브트리의 결과입니다. 예를 들어 맨 마지막 리프노드..
https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 처음에 뭔가 수학에서의 조합을 이용해 풀 수 있을 것 같았는데 제 아이디어로는 빌딩 사이로 1개만 넣는 거라 고민 끝에 다른 분들의 아이디어를 참고했습니다. 아이디어 : dp[n+1][l][r] 을 구하자 (n+1 : 전체 빌딩, l : 왼쪽에서 본 빌딩 수, r : 오른쪽에서 본 빌딩 수) 결론부터 말하자면 dp[n+1][l][r] = dp[n][l-1][r] + dp[n][l][r-1] + d..
https://www.acmicpc.net/problem/1765 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net 그냥 이름이 재밌어 보여서 풀어보았는데 그래프 문제였습니다. 앞서 푼 문제를 dfs로 풀어서 이번에는 bfs로 풀었습니다. 닭싸움 할 때 팀을 알아야 하는 문제입니다. 최대 팀의 개수를 구하면 됩니다. 친구의 친구도 친구이고, 원수의 원수도 친구입니다. 그리고 팀은 모두 친구로 구성됩니다. 그러므로 원래 친구였던 그래프는 그대로 두고, 원수였던 그래프만 한 단계 건너 탐색하면 됩니다. 그렇게 탐색이 완료된 그래프에서 bfs로 계속 친구들을 탐색하여 탐색이 마무리되면 한 ..