2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 읽기 해당 문제는 최단 경로를 구하는 문제라 판단하고 그리 어렵지 않을 것이라 생각했다. 하지만 20퍼센트 쯤에서 본 “틀렸습니다”라는 문구..!! 일단 문제 풀이를 시작해보자. 문제 풀기 NxM 크기의 일반적인 맵에 0으로 표현된 빈 칸, 1로 표현된 벽이 존재한다. 0, 0에서 N-1, M-1까지 가는 최단 거리를 찾으면서, 그 중에서 벽 한 개는 뚫을 수 있다. 이는 크게 어렵지 않게 생각했다. 최단 거리이기 때문에 DFS와 ..

9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제 읽기 일단 해당 문제를 읽고 나서는 완전 탐색 말고는 딱히 방법이 떠오르지는 않았다. 그래서 DFS와 BFS를 생각했고, DFS는 깊이 우선 탐색이라 끝이 없을 것 같아서.. 백퍼 시간 초과 날 거 같았다. 그래서 최소 연산의 개수를 구하는 것이기 때문에 BFS를 바로 적용해서 해결했다. 문제 풀기 문제는 크게 어렵지 않다. 주어진 명령어마다 요구사항에 따라서 정확하게 구현한다면 틀리지는 않을 것이다. 또한 같은 숫자로 또 탐색하지 않도록 하기..

13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 읽기 해당 문제는 가장 빨리 갈 수 있는 시간, 그리고 그 때의 루트를 출력해야 한다. 이전에 가장 빨리 갈 수 있는 시간을 문제는 풀어봤던 기억이 있다. 하지만 이 문제는 루트까지 출력해야 한다! 즉, BFS + 루트 출력 문제라 볼 수 있다. 문제 풀기 BFS를 쓰는 이유는, 당연하겠지만 최소 시간을 구하기 때문이다. 이 문제는 완전 탐색을 해야 하는데, DFS, BFS 중에서 고르라면 최소 시간만 얻으면 되기 때문에 주..

2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 읽기 이 문제는 일단 입력 값이 너무 컸기 때문에 바로 이분 탐색을 써야 겠다고 생각이 들었다. 입력 값을 한번 보자. 나무의 수 N : 1~1,000,000(백만) 필요한 나무 길이 M : 1 ~ 2,000,000,000(이십억) 나무의 높이 : 0~1,000,000,000(십억) 만약 완전 나이브하게 풀이한다면, 나무를 자를 높이를 0에서부터 십억까지 1씩 증가시키면서, N개의 나무를 다 잘라보고, 총합이 필요한 ..

9177번: 단어 섞기 입력의 첫 번째 줄에는 1부터 1000까지의 양의 정수 하나가 주어지며 데이터 집합의 개수를 뜻한다. 각 데이터집합의 처리과정은 동일하다고 하자. 각 데이터집합에 대해, 세 개의 단어로 이루어 www.acmicpc.net 문제 읽기 문제를 처음에 읽었을 때에는 모든 경우의 수를 따지는 방법을 생각했다. 단순하게 생각하면 dfs가 직관적이라 dfs를 생각했지만, 복잡도를 생각했을 때 단어의 길이가 200이기 때문에 dfs를 수행하면 지수 시간이기 때문에 불가능했다. 그래서 bfs로 접근했다. 문제 풀기 bfs로 풀었는데, 사실 처음에는 visited가 필요 없다고 생각했다. 처음에 다음 그림을 그렸었다. 이렇게 오른쪽, 아래쪽 두 방향으로 내려가면 경우의 수를 구했을 때 방문 처리는..

12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 문제 읽기 처음 문제를 읽고 예제를 한 번 그려봤다. 위와 같은 과정을 통해서 이루어진다면 돌이 정확히 분배된다. 위에서 알 수 있는 점은, 세 그룹에 있는 돌의 합이 3으로 나누어 떨어지지 않는다면 무조건 0을 출력한다는 점과, 이 문제는 다른 알고리즘 보다는 완전 탐색을 해야 할 것 같다는 느낌(?)이다. 그래서 완전 탐색인 DFS를 통해서 풀어보았다. 문제 풀기 처음 작성했던 풀이 과정은 크게 복잡하진 않았다. 우선 세 그룹을 두 그룹씩 개수를 비교해서..