DFS32 [백준] 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. [백준] 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. [백준] 9466번 - 텀 프로젝트 [Java] https://www.acmicpc.net/problem/9466 1. 아이디어 유방향 그래프에서 사이클에 속하지 않는 학생의 수를 구하는 문제가 된다. DFS 알고리즘과 위상 정렬을 활용하면 해결할 수 있다.2. 문제풀이 DFS는 각 점에 대해 매번 탐색을 하면 중복되는 사이클이 있는 그래프에 반복 접근하게 되고 이 부분에서 시간초과가 발생하게 된다. 이를 방지하기 위해 임시 방문과 실제 방문 두 가지 방문 체크를 활용해서 임시 방문으로 사이클 여부를 파악 후 사이클이 존재하면 사이클의 크기를 구한 후 실제 방문 처리를 하는 방식으로 구현했다. 위상 정렬은 사이클이 존재하면 정렬할 수 없는 점을 활용해서 정렬된 노드의 개수가 사이클을 이루지 못한 학생의 수가 됨을 활용했다.3. 코드 import ja.. 2025. 2. 10. [백준] 9205번 - 맥주 마시면서 걸어가기 [Java] https://www.acmicpc.net/problem/9205 1. 아이디어 상근이네 집과 편의점들, 펜타포트 락 페스티벌을 노드로 각 노드간 거리를 간선으로 하는 그래프에서 두 노드가 연결되었는지 판단하는 문제가 된다. 맥주 1병에 50미터씩 총 1000미터를 한번에 이동할 수 있으므로 간선의 길이가 1000이하인 간선만으로 그래프를 구성한 후 BFS, DFS 알고리즘으로 연결 여부를 파악하면 간단하게 해결할 수 있다.2. 문제풀이 거리가 맨해튼 거리이므로 Math.abs 메서드를 활용했고 상근이네 집을 출발점, 펜타포트 락 페스티벌을 도착점으로 탐색해서 도착할 수 있으면 true, 도착할 수 없으면 false를 반환하는 방식으로 구현했다.3. 코드 import java.io.*;import ja.. 2025. 2. 10. [소프티어] 6248번 - 출퇴근길 [Java] https://softeer.ai/practice/6248 1. 아이디어 시작점에서 방문할 수 있는 점들은 DFS 알고리즘으로 간단하게 구할 수 있다. 이때 다른 점들에서 도착점을 갈 수 있는지 여부는 역방향 간선을 활용해서 도착점에서 역방향 간선으로 DFS 알고리즘을 적용하면 간단하게 구할 수 있다.2. 문제풀이 동환이의 집에서 출근길에 포함되는 점들은 동환이의 집에서 DFS 알고리즘으로 방문 가능한 정점을 찾고 다시 방문 가능한 점들이 회사에 갈 수 있는지 찾으면 구할 수 있다. 하지만 처음 동환이가 찾은 방문 가능한 정점의 수가 늘어날 수록 DFS 알고리즘을 반복적으로 적용해야해서 시간초과가 발생하게 된다. 이를 해결하기 위해 동환이의 집에서 출근길에 포함되는 점들을 DFS 알고리즘으로 찾은 후.. 2025. 2. 10. [소프티어] 6275번 - 로봇이 지나간 경로 [Java] https://softeer.ai/practice/6275 1. 아이디어 방문한 곳을 다시 방문하지 않으면서 좌우 회전과 바라보는 방향으로 두 칸 이동하는 로봇의 움직임은 폐곡선을 만들지 않으면서 한붓그리기가 가능한 경로로 움직이게 된다. 따라서 방문한 칸이면서 사방에 방문한 칸이 한칸 밖에 없는 지점 두 개가 가능한 출발지가 된다. 해당 출발지에서 DFS 알고리즘을 통해 위치와 방향을 들고 다니며 명령을 구하는 방식으로 구현했다.2. 문제풀이 입력을 받은 후 시작 위치와 방향을 먼저 찾았다. 맵을 순회하며 방문한 칸일 때 사방에 방문한 칸이 하나밖에 없는 곳이면 시작 위치와 방향을 구한 후 종료했고 이후 해당 정보로 DFS 탐색을 시작했다. DFS는 방문 후 다음 위치를 찾을 때 다음 위치와 현재 .. 2025. 2. 7. [백준] 14267번 - 회사 문화 1 [Java] https://www.acmicpc.net/problem/14267 1. 아이디어 각 칭찬마다 직원들의 칭찬 수치를 갱신하면 시간 초과가 발생한다. 각 직원마다 최초로 칭찬을 받은 경우 칭찬 수치를 더한 후 한번에 계산하는 방식으로 해결할 수 있다.2. 문제풀이 Bottom-Up 다이나믹 프로그래밍과 DFS 알고리즘으로 해결이 가능했는데 다이나믹 프로그래밍은 주어진 직속상사 정보를 바로 활용해서 현재 직원의 칭찬 수치는 현재 직원이 최초로 받은 칭찬 수치의 합과 현재 직원의 부모 직원이 받은 칭찬 수치이다. 상사의 번호가 직원의 번호보다 항상 작아서 해당 방식으로 해결할 수 있었다. DFS는 그냥 사장부터 탐색하며 파라미터로 칭찬 수치의 합을 들고 다니면 간단하게 해결할 수 있다.3. 코드 packag.. 2025. 2. 6. [소프티어] 6246번 - 순서대로 방문하기 [Java] https://softeer.ai/practice/6246 1. 아이디어 N의 크기가 매우 작은 문제로 DFS 알고리즘을 활용하면 해결할 수 있는데 이때 방문해야하는 순서를 지키면서 모두 방문을 해야한다. 이를 위해 주어진 맵과 같은 크기의 맵에 방문해야하는 위치에 방문 순서를 저장한 pathOrder 2차원 배열을 활용해서 DFS에서 다음에 방문할 장소가 방문해야하는 지점이 아니면 일반 DFS를 적용하고 방문해야하는 장소면 순서가 맞는지 고려하는 방식으로 해결했다.2. 문제풀이 모든 경로를 탐색하기 위해 방문 체크 후 방문 체크 해제를 하는 DFS를 적용했다. 사방탐색을 하며 맵 바깥이거나 벽이거나 방문한 곳이면 넘어갔는데 그러면 탐색할 수 있는 장소는 일반 장소거나 방문해야하는 장소 두가지가 남는다.. 2025. 2. 6. [백준] 14248번 - 점프 점프 [Java] https://www.acmicpc.net/problem/14248 1. 아이디어 BFS와 DFS 알고리즘을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 시작 위치에서 왼쪽 또는 오른쪽으로 점프를 하고 다시 이동한 위치에서 왼쪽 또는 오른쪽으로 이동하는 것을 반복하는 문제로 점프할 위치가 방문 가능한 위치인지만 체크하는 BFS, DFS로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sys.. 2025. 2. 4. 이전 1 2 3 다음
