문제https://www.acmicpc.net/problem/28069 여담0번째 계단에서 순간이동을 하면 제자리 위치라는 것을 알아차리지 못했다. 전에도 이 문제를 풀었는데 모르겠어서 그냥 풀이를 참고해서 풀고 넘어갔더니 제대로 익히지 못한 것 같다. 이번에는 꼭 다시 풀어봐야지!  풀이문제에 따르면 계단을 올라갈 수 있는 방법은 총 2가지이다. 한 칸 올라가기i + i / 2 계단으로 순간이동하기 정확히 K번째 행동에서 N번째 계단에 도달해야 미니 김밥을 먹을 수 있다고 한다. 이때, 0번 계단에서 2번 연산을 수행하면 제자리에 위치하게 된다. (0 + 0 / 2 = 0)  즉, N = 2, K = 4일 때  2번만에 N번째 계단에 도착할 수 있다면 다음과 같은 연산을 수행하면 되는 것이다. 0번 계..

문제https://www.acmicpc.net/problem/2251 여담"물을 옮기는 모든 경우를 탐색하지 않고 더 쉬운 방법이나 규칙이 있지 않을까?"라는 생각으로 삽질했다..ㅎㅎ 한 번 다른 길로 빠지면 올바른 길로 돌아오기가 너무 어렵다. 처음부터 방향을 잘 잡도록 문제를 많이 풀어봐야지..!  풀이이 문제는 한 물통에서 다른 물통으로 물을 쏟아 붓는 과정을 반복하고, 물통 A가 비었을 때 물통 C의 용량을 기록하는 문제이다. 물통은 총 세 개이므로, 하나의 물통에서 다른 물통으로 물을 쏟아 붓는 경우는 총 6가지이다. 따라서 각각의 경우를 큐에 넣고 BFS 탐색을 수행하면 된다.A → BA  → CB  → AB  → CC  → AC  → B BFS 탐색 시, 이미 확인한 경우를 다시 탐색하지 않..

문제https://www.acmicpc.net/problem/2573 여담2차원 배열도 clone() 메서드를 사용하면 내용만 복제가 되는 줄 알고 사용했었다.. 그런데 답이 이상하게 나와서 확인해보니 arr 배열 값을 변경하면 map 배열 값도 변경된다는 것을 알게 되었다. clone() 메서드에 대해 검색하니 2차원 배열에는 사용할 수 없다는 것을 알게 되었다..ㅎ  전에도 이런 일이 있었던 것 같은데.. 🤦🏻‍♀️ 제발 기억하자! 1차원 배열 복제는 clone(), 2차원 배열 복제는 직접하기! 풀이빙산이 최초로 분리되는 시간을 구하기 위해서 "빙산 녹음 → 빙산의 수 확인" 과정을 반복하면 된다. 빙산의 수가 0개 또는 2개 이상일 때 반복을 종료하면 된다. 즉, 다음의 과정을 반복하면 된다...

문제https://www.acmicpc.net/problem/16234 여담BFS에 구현이 포함된 문제라 조건을 빼뜨리지 않도록 주의해서 풀어야 할 것 같다. 이런 문제가 나오면 우선 풀이 순서를 정리하고 풀도록 하자. 풀이국경선이 열려있는 나라를 찾기 위해 BFS 탐색을 수행하면 된다. 인구 이동이 없을 때까지 풀이 과정은 다음과 같다.방문하지 않은 나라에 대해 다음의 과정을 수행한다.해당 나라에 대해 BFS 탐색을 수행한다.국경선을 공유하는 나라와 인구 차이가 L명 이상, R명 이하라면 연합 목록에 저장하고 큐에 넣는다. 이때, 연합의 인구 수를 조정해야 하므로 인구수도 기록한다.   연합 목록에 저장: unionList.add(new Pos(nx, ny)) 인구 수 기록: total += map[n..

문제https://www.acmicpc.net/problem/7562 여담처음에 방문 배열을 사용해서 풀었는데, 방문 배열을 사용하지 않고 거리를 기록한 배열로도 방문 체크를 할 수 있었다. 꼼꼼히 확인하고 풀자.. 풀이나이트가 움직일 수 있는 방향은 총 8가지로, 최종 위치에 도달할 때까지 이동할 수 있는 모든 방향으로 탐색해야 한다. 나이트의 최소 이동 횟수를 구하는 문제이기 때문에, BFS를 사용하여 각각의 칸을 탐색할 때마다 걸린 이동 횟수를 기록하면 된다. map[nx][ny] = map[x][y] + 1 (0, 0) 에서 (7, 0) 까지의 최소 이동 횟수를 구하는 예시는 다음과 같다. 코드import java.io.*;import java.util.*;public class Main { ..

문제https://www.acmicpc.net/problem/2583 여담좌표를 주의해야 한다.. 생각없이 풀다가 좌표를 잘못 설정해서 틀릴 뻔 했다. 칸을 기준으로 좌표를 생각하면 쉽게 풀 수 있다.  풀이직사각형이 그려진 위치를 1, 그려지지 않은 위치를 0으로 설정하여 map[x][y] == 0인 부분을 BFS 또는 DFS 방식으로 탐색하면 된다. 총 탐색 횟수 == BFS 또는 DFS 탐색 횟수각 영역의 넓이 == 탐색 시 좌표를 방문하는 횟수 다음과 같이 직사각형이 그려져있는 경우에는 (0, 0), (0, 4), (2, 4)에서 탐색을 시작하면 된다. 코드BFS 탐색import java.io.*;import java.util.*;public class Main { static int M, ..

문제https://www.acmicpc.net/problem/11725 여담방문을 확인하는 배열과 부모 노드를 기록하는 배열을 따로 사용하지 않고 하나로 합칠 수 있다. 굳이 방문 확인 배열이 필요하지 않다면  사용하지 말자! 풀이BFS 탐색을 사용하여 문제를 풀이하면 된다. 우선 자신과 연결된 노드를 인접 리스트에 저장한다. 그 후, 루트 노드인 1번을 시작으로 BFS 탐색을 시작하면 된다.  부모에서 자식 방향으로 탐색을 수행하는 것으로, 자식에서 부모를 탐색하지 않도록 이미 탐색이 끝난 것은 부모 노드를 기록하여 다시 탐색하지 않도록 해야 한다. root[x]가 0인 경우아직 탐색을 하지 않은 노드root[x]가 0이 아닌 경우이미 탐색이 끝난 노드주의해야 할 점은 N의 최댓값이 100,000이라는..

문제https://www.acmicpc.net/problem/2468 여담"아무 지역도 물에 잠기지 않을 수 있다"라는 조건을 놓칠 뻔했다.. 문제를 끝까지 잘 읽어야지..ㅎ 풀이BFS 탐색을 통해 풀이할 수 있다. 장마철에 내리는 비의 양을 최소 높이 ~ 최대 높이-1로 설정하고, 각 높이마다 BFS 탐색을 수행하면 된다. BFS 탐색을 수행하는 조건은 다음과 같다.배열의 값이 비의 양보다 많은 경우map[i][j] 해당 위치를 방문하지 않은 경우!visited[i][j]안전한 영역의 개수는 각 높이에서 BFS 탐색을 수행하는 횟수를 뜻하므로, 각 높이마다 최댓값을 갱신하면 된다. 이때, 아무 지역도 물에 잠기지 않을 수 있으니 최댓값을 기록하는 변수는 1로 초기화를 해야 한다.  코드import ja..

문제https://www.acmicpc.net/problem/1697 여담N과 K가 같을 때를 생각하지 못하고 풀었다가 틀렸었다. 여러 반례들을 잘 생각해보고 제출하자..! 풀이수빈이의 위치를 배열의 인덱스로 정하고, 이동할 때마다 그 횟수를 배열에 기록하면 된다.예시를 살펴보자. 0초인 경우N이 5이므로, 인덱스 5에 1을 저장한다.  1초인 경우1초 후, 이동 가능한 X - 1, X + 1, 2 * X 위치에 이전 값(=dist[5])에 1을 더한 값인 2를 저장한다. 2초인 경우1초일 때 나올 수 있는 X는 4, 6, 10으로 총 3가지이다. 그중에서 인덱스 4를 예시로 살펴보겠다. X - 1의 위치는 3, X + 1의 위치는 5,  2 * X 의 위치는 8이다. 인덱스 3 : 방문하지 않음 ⇒ 3..

문제https://www.acmicpc.net/problem/16953 여담처음에는 int 배열을 사용해서 연산의 횟수를 기록했다. 그러나 B의 크기가 최대 10억이므로 메모리 초과가 발생했다. 그래서 배열을 사용하지 않고 그냥 연산의 횟수를 사용하기 위한 변수를 선언해서 사용했다. 이때까지 메모리 조건은 제대로 확인하지 않고 넘겼는데.. 메모리 계산의 필요성을 느꼈다. 풀이"2를 곱하는 경우"와 "오른쪽에 1을 더하는 경우"로 나누어서 풀이하면 아래 사진과 같은 트리 모습이 나온다. 따라서 BFS 탐색을 사용해서 A가 B와 처음으로 같은 경우, 즉 연산의 최솟값을 구하면 된다.  코드import java.io.*;import java.util.*;public class Main { public s..