[BaekJoon] #14442 - 벽 부수고 이동하기 2 [Java][C++]
문제 링크 1. 아이디어 BaekJoon 2206번 - 벽 부수고 이동하기 문제에서 벽을 부술 수 있는 횟수가 최대 $K$번인 문제로 조건만 살짝 수정하면 동일하게 해결할 수 있다. 2. 복잡도 접근 시간 공간 풀이 $O(K \times ...
문제 링크 1. 아이디어 BaekJoon 2206번 - 벽 부수고 이동하기 문제에서 벽을 부술 수 있는 횟수가 최대 $K$번인 문제로 조건만 살짝 수정하면 동일하게 해결할 수 있다. 2. 복잡도 접근 시간 공간 풀이 $O(K \times ...
문제 링크 1. 아이디어 양방향 간선들이 주어진 그래프에 대해 너비 우선 탐색을 하면 되는 문제로 인접 리스트를 활용하면 되며, 오름차순 방문을 위해 정렬을 한 번 했다. 2. 복잡도 접근 시간 공간 풀이 $O(N + E \log E)$ ...
문제 링크 1. 아이디어 캠퍼스에서의 도연이의 위치에서부터 BFS나 DFS를 통해 빈 공간이나 사람이 있는 위치로 탐색을 이어나가며 사람이면 개수를 세면 된다. 2. 복잡도 접근 시간 공간 BFS $O(N \times M)$ $...
문제 링크 1. 아이디어 물과 닿은 얼음은 매일 녹을 때 며칠 후 두 백조가 만날 수 있는지 구하는 문제로 단순히 얼음을 녹이고 백조가 만날 수 있는지 찾는 방식을 반복하는 것으로는 시간 내에 해결할 수 없다. 호수의 각 얼음에 대해 해당 얼음이 며칠 뒤에 녹는지를 전부 구한 후 매개변수 이분 탐색을 통해 두 백조가 만날 수 있는 날을 탐색하...
문제 링크 1. 아이디어 운동장의 둘레의 길이는 직사각형의 가로 두 변의 길이와 두 반원의 호의 길이의 합과 같다. 2. 복잡도 접근 시간 공간 풀이 $O(1)$ $O(1)$ 3. 코드 풀이 [Java][...
문제 링크 1. 아이디어 원숭이는 기본적으로 상하좌우로만 움직일 수 있지만 최대 $K$번은 말처럼 움직일 수 있다. 최단 거리 BFS를 통해 해결할 수 있는데 이때 특정 좌표를 단순히 방문하는 것만 체크하는 게 아니라 말처럼 몇 번 움직여서 방문했는지를 체크하면 두 움직임을 조합한 최단 거리를 구할 수 있다. 이를 위해 3차원 배열로 방문 체...
문제 링크 1. 아이디어 CCTV 한 대는 $N \times N$ 크기의 영역을 커버할 수 있다. 대회장의 크기는 입력으로 세로 $R$, 가로 $C$ 순서로 주어지지만 직관적인 설명을 위해 $R$을 가로, $C$를 세로로 두고 서술한다. 따라서 주어진 대회장의 가로에는 $R / N$을 올림 나눗셈한 만큼 배치를 해야 하고, 세로에는 $C / ...
문제 링크 1. 아이디어 각 버튼이 서로 배수, 약수 관계에 있어서 최소 조작을 하려면 지정된 시간이 큰 버튼부터 누르면 된다. 지정된 시간이 가장 작은 버튼이 10초를 더하므로 초기 요리시간을 10으로 나눈 나머지가 0이 아니면 불가능한 경우이다. 2. 복잡도 접근 시간 공간 ...
문제 링크 1. 아이디어 주어진 창고에서 익은 토마토 옆의 토마토는 다음 날 익은 토마토가 되며 초기 익은 토마토의 위치가 주어진다. 시작점이 여러 개인 BFS를 활용하면 해결할 수 있는데 초기 익은 토마토를 큐에 넣은 후 BFS를 수행하면 되며 안 익은 토마토인데 방문하지 못했다면 모든 토마토를 익힐 수 없다. 날짜도 구해야 하므로 레벨 B...
문제 링크 1. 아이디어 BaekJoon 7576번 - 토마토 문제에서 토마토가 수직으로도 쌓여있는 문제로 육방 탐색을 활용하기만 하면 동일한 아이디어로 해결할 수 있다. 2. 복잡도 접근 시간 공간 풀이 $O(N \times M \tim...