기록방

👉 문제링크 🔸 문제 분석 🔸 이진 검색 트리의 전위 순회 결과를 토대로 후위 순회 결과를 출력한다. 🔸 문제 풀이 🔸 전위 순회 결과를 EOF(End Of File : null)가 나올 때까지 입력받는다. 첫 번째 결과는 Root 로 사용한다. 이후 결과는 작으면 왼쪽 자식 노드, 크면 오른쪽 자식 노드로 구분해 재귀 메서드를 호출하고 저장한다. 전위 순회 결과로 만들어진 이진 검색 트리를 후위 순회 방식으로 재탐색하여 결과를 출력한다. 전위 순회와 비슷하지만, 탐색 순서만 변경하면 된다. 🔸 코드 🔸 import java.io.*; public class Main { private static class Node { private final int root; private Node left; priv..

👉 문제링크 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 🔸 문제 분석 🔸 N * M 행렬 맵에서 (1, 1)부터 (N, M) 까지 이동하는 최단거리를 구한다. 인접한 상하좌우로 1칸씩 이동할 수 있다. 이동할 수 있는 칸은 0, 벽은 1로 표시되는데, 1번 벽을 부수고 이동할 수 있다. 행렬에서 최단거리를 구하는 문제이므로 BFS를 사용한다. 벽을 부수고 먼저 도착했었던 칸을 벽을 부수지 않고 도착했다면, 이어서 탐색해보아야 한다. 벽을 부수지않고 먼저 도착했던 칸이면 더 탐색해..

👉 문제링크 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 🔸 문제 분석 🔸 노드 사이 거리(가중치)가 있는 트리에서 가장 먼 거리를 구한다. 어느 부분 가중치가 큰 값이든 트리의 지름 양 끝은 리프 노드일 것이다. (큰 가중치 부분을 반드시 지남) 트리이기 때문에 두 노드 사이의 경로는 하나로 유일하다. 한 노드에서 가장 먼 노드를 구하면, 그 노드가 트리의 지름 양 끝 리프 노드 중 하나이다. DFS 두 번으로 풀이할 수 있다. DFS 1 : 아무 노드에서 가장 먼 노드를 구한다. DFS..

👉 문제링크 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 🔸 문제 분석 🔸 문제 내용 N명의 사람과 M개의 파티가 있다. 진실을 아는 사람이 참여한 파티에서는 진실만 말해야 한다. 진실을 말한 파티에 있던 사람들도 진실을 아는 사람이 된다. 거짓을 말할 수 있는 파티의 수를 출력한다. 풀이 전략 같은 파티 참가자를 연결해야 한다. 각 파티별 참가자 List와 개인 별 참가 파티 List를 만든다. BFS로 진실을 말한 파티와 진실을 알게된 사람들을 추가해 나간다. 진실을 말하지 않은 파티의 수를 출력한다. 2024...

👉 문제링크 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 🔸 문제 분석 🔸 육지는 상하좌우로 건널 수 있는 땅이다. 두 보물은 한 육지에 있으며, 최단 거리가 가장 긴 두 위치에 있다. bfs로 가장 멀리 퍼진곳을 찾으면, 최단 거리 중 가장 긴 거리이다. 두 보물 사이를 이동하는 시간을 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Ar..