그래프115 [백준] 1976번 - 여행 가자 [Java] https://www.acmicpc.net/problem/1976 1. 아이디어 여행을 가려는 도시가 모드 하나의 그래프 안에만 있으면 되므로 유니온 파인드 알고리즘으로 해결할 수 있다.2. 문제풀이 union 연산으로 그래프를 구성한 후 Set을 활용해 여행가려는 각 도시의 그룹장을 저장했다.Set의 크기가 1이면 모든 도시가 하나의 그래프 안에 있는 것이므로 여행을 갈 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { private static int[] p; private static int[] make(int N) { int[] arr = new int[1 + N]; for (int i = .. 2025. 3. 20. [백준] 1043번 - 거짓말 [Java] https://www.acmicpc.net/problem/1043 1. 아이디어 유니온 파인드 알고리즘을 통해 각 파티를 집합으로 표현한 후 각 파티의 그룹장만 따로 담아준다.이후 각 파티의 그룹장이 진실을 아는 지 판단했다.2. 문제풀이 진실을 아는 사람은 부모의 번호를 0번으로 설정했고 파티의 그룹장은 번호가 작은 사람이 오도록 했다.유니온 파인드 알고리즘을 통해 그룹을 형성한 후 그룹장만 따로 Queue에 담아줬다.이러면 Queue의 그룹장의 부모(최고 조상)이 0인지 여부로 그룹에 진실을 말해야하는지 간단하게 판단할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { private static int[] p; priv.. 2025. 3. 20. [프로그래머스] 118669번 - 등산코스 정하기 [Java] https://school.programmers.co.kr/learn/courses/30/lessons/118669 문제 설명 XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다. 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다. 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다. 등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현할 수 있습니다.예를 들어 1-2-3-2-1 으로 표현하는 등산코스는 1번지점에서 출발하여 2번, 3번, 2번, 1번 지점을 순서대로 방문한다는 뜻입니다.등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수.. 2025. 3. 6. [백준] 23290번 - 마법사 상어와 복제 [Java] https://www.acmicpc.net/problem/23290 1. 아이디어 마법 연습의 각 작업을 메서드로 분리하고 조립해서 로직을 구현하는 방식으로 접근했다.2. 문제풀이 물고기는 위치와 방향을 담은 객체로 관리하며 Queue로 다뤘다.각 위치의 물고기 수를 저장하기 위한 카운팅 맵과 각 위치에서 냄새의 남은 시간을 저장하기 위한 카운팅 맵을 활용했다.작업 1은 작업 5에서 복제를 하기 위해 현재 물고기 정보를 따로 보관해야한다.작업 2는 물고기의 이동으로 델타배열을 통해 회전을 구현하고 상어 위치와 냄새 위치를 기록해서 구현하면 된다.작업 3은 상어의 이동으로 DFS 알고리즘을 통한 완전 탐색으로 진행했고 방문 체크 및 방문 해제로 물고기를 중복으로 제외하지 않게 주의하면서 탐색했고 가장 많.. 2025. 2. 24. [백준] 20058번 - 마법사 상어와 파이어스톰 [Java] https://www.acmicpc.net/problem/20058 1. 아이디어 2차원 배열의 회전, 얼음의 양 줄이기, 가장 큰 얼음 덩어리의 크기를 각각 구현해서 합치면 되는 문제로 2차원 배열의 회전읜 격자의 크기와 동일한 크기의 배열과 인덱스의 활용으로, 얼음 양 줄이기는 Queue를 활용해서, 가장 큰 얼음 덩어리의 크기는 BFS, DFS 알고리즘으로 구할 수 있다.2. 문제풀이 얼음판의 크기는 2^N으로 주어지는데 편의를 위해 N을 2^N으로 바꿔서 이용했다. 이를 위해 비트 연산자를 활용했다. 격자의 크기 역시 비트 연산으로 L을 2^L로 바뀌줬고 이후 회전 메서드에서 이용했다. 회전은 두 2차원 배열의 크기가 다른 점만 주의해서 구현하면 된다. 얼음의 양 줄이기는 사방탐색으로 줄여야 하.. 2025. 2. 23. [프로그래머스] 150367번 - 표현 가능한 이진트리 [Java] https://school.programmers.co.kr/learn/courses/30/lessons/150367 문제 설명 당신은 이진트리를 수로 표현하는 것을 좋아합니다. 이진트리를 수로 표현하는 방법은 다음과 같습니다. 이진수를 저장할 빈 문자열을 생성합니다.주어진 이진트리에 더미 노드를 추가하여 포화 이진트리로 만듭니다. 루트 노드는 그대로 유지합니다.만들어진 포화 이진트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.문자열에 저장된 이진수를 십진수로 변환합니다.이진트리에서 .. 2025. 2. 22. [백준] 1388번 - 바닥 장식 [Java] https://www.acmicpc.net/problem/1388 1. 아이디어 이어진 '-' 또는 '|'가 하나의 판자가 되는 상황으로 2차원 배열의 순회로 간단하게 해결할 수 있다.2. 문제풀이 '-', '|'를 발견하면 가로 또는 세로방향으로 이어진 부분을 전부 찾아서 ' '으로 변경하고 판자의 개수를 세는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final char EMPTY = '\u0000'; public static void main(String[] args) throws IOException { BufferedReader br = new Buffere.. 2025. 2. 12. [백준] 2573번 - 빙산 [Java] https://www.acmicpc.net/problem/2573 1. 아이디어 빙산을 녹이는 로직과 빙산의 개수를 구하는 로직을 구분해서 해결했다. 빙산의 개수는 BFS, DFS 알고리즘으로 간단하게 구할 수 있다.2. 문제풀이 빙산을 녹일 때 방금 녹여서 바닷물이 된 부분이 다시 옆 빙산을 녹이는 상황이 발생하게 돼서 각 빙산 주변의 바닷물을 따로 센 후 한번에 빼주는 것만 주의해서 구현하면 된다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { private static final int[] dr = {-1, 0, 1, 0}; private static final int[] dc = {0, 1, 0, -1}; pu.. 2025. 2. 11. [백준] 17472번 - 다리 만들기 2 [Java] https://www.acmicpc.net/problem/17472 1. 아이디어 BFS, DFS 알고리즘으로 각 섬에 대해 번호를 매긴 후 설치할 수 있는 모든 다리를 찾아서 섬은 노드, 다리를 간선으로 하는 최소 스패닝 트리를 구하는 방식으로 해결했다.2. 문제풀이 각 섬에 번호를 붙여서 섬들을 구분하려고 했고 지도를 순회하며 섬을 발견하면 BFS, DFS 알고리즘으로 해당 섬 전체에 번호를 부여했다. 이후 지도를 순회하며 현재 위치가 섬이면서 오른쪽이 바다인 경우, 현재 위치가 섬이면서 아래쪽이 바다인 경우, 다시 섬을 발견할 때까지 해당 방향으로 계속 가며 섬을 발견하면 이 정보로 다리를 생성해서 우선순위 큐에 넣어줬다. 이후 이 우선순위 큐로 크루스칼 알고리즘을 돌려 모든 섬을 연결하는 다리 .. 2025. 2. 11. [백준] 2146번 - 다리 만들기 [Java] https://www.acmicpc.net/problem/2146 1. 아이디어 BFS 알고리즘으로 각 섬에 대해 번호를 매긴 후 다시 각 섬의 경계부터 다른 섬을 찾을 때까지 최단 거리 BFS를 적용하는 것을 각 섬에 대해 반복해서 해결했다.2. 문제풀이 각 섬에 번호를 붙여서 서로 다른 두 섬을 구분하려고 했다. 입력에서 섬은 1로 주어져 있어서 구분을 위해 번호를 2번부터 매겼으며 해당 섬에 번호를 붙이면서 해당 섬의 경계인 바다는 따로 Queue에 담아줬다. 이후 해당 Queue로 다시 최단거리 BFS를 적용해서 해당 섬이 아닌 좌표를 담아주며 다른 섬을 발견하면 최단 거리를 반환하게 했다.3. 코드 import java.io.*;import java.util.*;public class Main.. 2025. 2. 11. [백준] 2887번 - 행성 터널 [Java] https://www.acmicpc.net/problem/2887 1. 아이디어 행성을 노드, 연결을 간선으로 하는 최소 스패닝 트리를 구하는 문제가 된다. N개의 행성에서 나올 수 있는 모든 연결은 총 N * (N-1) / 2개로 N이 최대 10만이라면 너무 많은 경우가 나오게 된다. 최소 스패닝 트리는 N-1개의 간선만 선택하면 되는데 이때 특정 축에 대해 좌표를 정렬한 후 서로 인접한 행성끼리 연결한다고 했을 때 N-1개의 연결이 나오고 이 연결로도 최소 스패닝 트리를 만들 수 있다.(인접하지 않은 행성들은 이 연결들로 찾으면 된다.) 따라서 각 축에 대해 모두 구한 3 * (N-1)개의 간선만으로 전체 행성에 대한 최소 스패닝 트리를 구할 수 있다.2. 문제풀이 행성 번호와 좌표를 담은 2차원 .. 2025. 2. 11. [백준] 16398번 - 행성 연결 [Java] https://www.acmicpc.net/problem/16398 1. 아이디어 행성을 노드, 플로우를 간선으로 하는 최소 스패닝 트리를 구하는 문제가 된다.2. 문제풀이 크루스칼 알고리즘으로 최소 스패닝 트리를 구하는 방식으로 구현했다. 이때 N이 1이 될 수 있는 점과 가중치의 합이 int형 오버플로우가 발생할 수 있는 점에 주의해야했다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Edge implements Comparable { int a; int b; int w; public Edge(int a, int b, int w) { .. 2025. 2. 11. 이전 1 2 3 4 ··· 10 다음
