[BaekJoon] #9019 - DSLR [Java][C++]
문제 링크 1. 아이디어 주어진 D, S, L, R 연산을 활용해서 $A$를 $B$로 바꾸는 최소 명령어 나열을 구하는 문제로 BFS와 역추적을 활용하면 해결할 수 있다. 먼저 주어진 명령어를 처리할 수 있어야 하는데 임의의 수 $n$에 대해 아래와 같이 각 명령어가 적용된 결과를 구할 수 있다. D: $(n \times 2) \bm...
문제 링크 1. 아이디어 주어진 D, S, L, R 연산을 활용해서 $A$를 $B$로 바꾸는 최소 명령어 나열을 구하는 문제로 BFS와 역추적을 활용하면 해결할 수 있다. 먼저 주어진 명령어를 처리할 수 있어야 하는데 임의의 수 $n$에 대해 아래와 같이 각 명령어가 적용된 결과를 구할 수 있다. D: $(n \times 2) \bm...
문제 링크 1. 아이디어 나이트의 이동으로 목적지에 갈 수 있는 최소 횟수를 구하는 문제로 최단거리 BFS를 활용하면 해결할 수 있다. 일반적인 격자 그래프에서의 사방 탐색이 아닌 나이트의 이동 방법에 맞춘 팔방 탐색을 활용하면 된다. 2. 복잡도 접근 시간 공간 ...
문제 링크 1. 아이디어 3차원 빌딩에서 목적지에 도달할 수 있는지, 도달할 수 있다면 몇 분이 걸리는지 구하는 문제로 3차원 탐색을 위한 육방 탐색을 활용한 BFS로 간단하게 해결할 수 있다. 2. 복잡도 접근 시간 공간 풀이 $O(T ...
문제 링크 1. 아이디어 1층 빌딩의 정보가 주어져 있을 때 훔쳐올 수 있는 문서의 최대 개수를 구하는 문제다. BFS를 활용하면 해결할 수 있는데 먼저 빌딩 외부에서 빌딩의 경계 중 통과할 수 있는 곳을 통해 진입한다는 점에서 빌딩 외부에 빈 공간으로 이루어진 패딩을 한 칸 주고 $(0, 0)$에서 탐색을 시작해서 시작점을 찾는 로직을 간소...
문제 링크 1. 아이디어 컴퓨터를 노드, 연결 정보를 간선으로 간주한 그래프에서 1번 노드와 직간접적으로 연결된 다른 노드의 수를 구하는 문제로 생각할 수 있다. BFS 또는 DFS를 활용해서 방문한 노드의 수를 카운팅하면 해결할 수 있다. 노드의 수가 크지 않아서 인접 행렬을 활용해서 구현했다. 2. 복잡도 ...
문제 링크 1. 아이디어 주어진 미로에서 이동할 수 있는 칸을 통해 $(1, 1)$에서 $(N, M)$까지 가는 최단거리를 구하는 문제로 사방 탐색과 BFS를 활용하면 간단하게 해결할 수 있다. 2차원 배열로 미로가 표현됐으므로 사방 탐색으로 다음에 이동할 후보지를 탐색하고, BFS는 큐의 크기만큼 탐색하면 등거리의 모든 후보를 탐색한다는 점...
문제 링크 1. 아이디어 주어진 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제로 정점 번호가 작은 것을 먼저 방문해야 한다. 인접 리스트를 활용했는데 이때 정점 번호가 작은 것을 먼저 방문할 수 있게 정렬했다. 인접 리스트의 경우 양방향 연결을 해야 함에 주의해야 한다. 2. 복잡도 접...
문제 링크 1. 아이디어 필요한 최소 배추흰지렁이 마리 수는 배추밭에서 연결된 배추들을 한 묶음으로 볼 때, 각 묶음당 한 마리씩 배치하면 된다. 따라서 배추밭의 각 좌표를 순회하며 배추면 해당 배추 묶음을 전부 방문 처리하고 묶음의 수를 세는 과정을 반복하면 된다. 방문 처리를 하면 같은 묶음을 한 번만 셀 수 있으며 구현할 때는 원본 배추...
문제 링크 1. 아이디어 크기가 10인 각 배열에서 3번째로 큰 수를 출력하는 문제로 주어진 배열을 오름차순으로 정렬했을 때, 8번째에 위치한 원소를 찾으면 된다. 2. 복잡도 접근 시간 공간 풀이 $O(T)$ $O(1)$ ...
문제 링크 1. 아이디어 다이나믹 프로그래밍을 활용해 1부터 특정 수를 만들기 위해 필요한 최소 연산 횟수를 구하면 간단하게 해결할 수 있다. 예를 들면 1은 어떤 연산 없이도 바로 만들 수 있으므로 dp[1] = 0이 되며 주어진 연산의 역으로 dp[1 * 3] = 1, dp[1 * 2] = 1, dp[1 + 1] = 1을 구할 수 있다. ...