[SWEA] 1824. 혁진이의 프로그램 검증📌 풀이 과정단순한 시뮬레이션 문제인줄 알았는데 무려 4차원 방문 배열이 필요한 문제였다.dfs 재귀로 계속 탐색하니 StackOverflow 가 떠서 골치가 아픈 문제다. 이동 방향에 따른 인덱스 관리하기문제에서는 이동 방향이 2차원 격자의 크기를 벗어날 경우 반대편에 있는 위치로 이동해야 한다.이때 모듈러 연산을 통해 인덱스 관리를 해야한다.우리가 일반적으로 사용하는 (index + 1) % size 방식은 음수 인덱스를 처리할 수 없으니index = (index - 1 + size) % size위 방식으로 음수 인덱스를 방지하여 순환할 수 있도록 한다. 4차원 방문배열이 왜 필요하지?이 문제의 목적은 혁진이는 자신이 작성한 프로그램이 결국에는 멈출 수 ..

[SWEA] 8382. 방향 전환 📌 풀이 과정이 문제는 규칙을 찾아서 수식으로 쉽게 풀 수 있다. 하지만 그래프 탐색을 연습해야 하기에 BFS로 풀게되었다. (x1, y1 )에서 (x2, y2)로 이동을 하는데 가장 첫 이동은 어떤 이동이어도 상관 없다.이전 이동이 가로 이동이었다면, 이번에는 세로 이동으로 이동하고, 이전 이동이 세로 이동이었다면,이번에는 가로 이동으로 이동하여 (x1, y1)에서 (x2, y2)로 이동해야 한다.여기서 최소 몇 번의 이동을 해야 도착할 수 있는지 구현을 해야 한다.가로와 세로 방향으로 번갈아 이동해야 하는 조건으로 인해 방향에 따른 방문 체크가 필요하다.즉, 같은 위치라도 직전에 가로로 이동했는지, 세로로 이동했는지에 따라그 다음 이동이 달라지기 때문에 방향 정보를..

[SWEA] 10966. 물놀이를 가자 📌 문제 풀이각 땅(L)에서 가장 가까운 물(W)까지의 최소 거리를 구하고, 그 거리들의 합을 계산해야 한다.처음에 문제에서 적힌 것 처럼 땅에서 출발해서 물에 도착하는 경우 그 거리를 누적하게 했는데 시간 초과가 떴다. 문제에선 물(W)의 개수가 최소 1개 이상 주어진다고 했지만,예외적으로 최악의 상황을 생각해보자!! 만약 물(W)이 아예 없다면, 땅(L) 위치에서 각각 BFS를 수행해도 물에 도착할 수 없게된다.이 경우 모든 땅에 대해 개별적으로 BFS를 수행해야 하므로, 땅의 개수만큼 BFS가 실행되어연산량이 크게 증가하고 최단 거리 계산이 불가능해진다.따라서 물(W)의 위치에서 출발해, 동시에 BFS를 수행하면서 땅(L)을 탐색하는 방식으로생각의 전환이 필..

[백준] 2636 치즈2636. 치즈 - 골드4📌 풀이 과정 외부 공기 (0,0) 위치를 시작점으로 bfs 탐색을 시작한다.현재 탐색할 대상인 위치가 1. 공기인 경우(0)큐에 넣어 다음 탐색에서도 이 공기와 연결된 좌표를 계속해서 탐색해 나갈 수 있도록 한다. 2. 치즈인 경우(1)탐색 중 이 좌표가 치즈라면, 외부 공기와 접촉한 것이므로 녹여야 한다.치즈를 공기(0)로 바꾸어 녹인 뒤, 남은 치즈 개수를 감소 시킨다. cheese--여기서 중요 포인트!!!녹인 치즈는 큐에 넣지 않는다.큐에 넣게 되면 새로 녹은 공기가 내부 공기와 접촉할 위험이 있기 때문에안쪽에 있는 치즈가 의도치 않게 녹을 수 있다.  ✨ 제출 코드package beakjoon;import java.io.BufferedReader..

[SWEA] 2115 벌꿀채취📌 풀이 과정두 명의 일꾼이 최대 수익을 얻을 수 있도록 꿀을 채취하는 구간을 선택해야 한다.각 일꾼이 채취할 수 있는 벌통의 수와 꿀의 최대 양이 정해져있기 때문에, 이 조건을 잘 생각해야 한다.각 구간에서 선택할 수 있는 벌통의 부분 집합 중에서 최대 수익을 미리 구해두면이후 두 일꾼이 벌통을 선택할 때 그 값을 재사용할 수 있기 때문에 최대 수익을 먼저 계산하도록 하자!!!아래 코드에서 profit 배열에 각 구간의 최대 수익을 미리 계산해두면두 일꾼이 벌통 구간을 선택할 때 해당 구간의 최대 수익만 참조하면 된다.1. 최대 수익 계산각 구간에서 얻을 수 있는 최대 수익을 계산해야 한다.일꾼이 꿀을 채취할 수 있는 모든 가능한 구간에 대해 최대 수익을 구한다.2. 두 ..

[SWEA] 5656. 벽돌 깨기 📌 풀이 과정1. 중복순열로 구슬 떨어뜨릴 위치 선택하기2. 구슬 떨어뜨리기3. 벽돌 파괴하기4. 빈칸 채우기 이 과정에 유의해서 차근차근 구현해 나가면 된다.구슬이 명중한 벽돌은 상하좌우로 (벽돌에 적힌 숫자 - 1)칸 만큼 같이 제거된다는 조건을 잊으면 안된다!! ✨ 제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Solution { static int N, W, H; static int totalOfBrick, count, result; static int[][]..

[SWEA] 1767. 프로세서 연결하기 📌 풀이 과정최대한 많은 Core에 전원을 연결하였을 경우, 전선 길이의 합을 구해야 한다.단, 여러 방법이 있을 경우, 전선 길이의 합이 최소가 되는 값을 구하는 것이 문제 조건이다.가장자리에 위치한 core는 전선을 연결하지 않기에 전선 연결에서 고려하지 않아도 된다.따라서 가장자리에 있는 core는 코어 목록에서 제외해도 된다.✨ 제출 코드메모리 : 22,048 kb시간 : 196 msimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.uti..

[SWEA] 5644. 무선 충전 📌 풀이 과정처음에는 BC의 범위를 관리하기 위해서 배열을 따로 두어야 하나? 고민을 했다.하지만, 이 문제에서 핵심은 특정 위치에서 어떤 BC가 사용 가능한지를 실시간으로 파악하는 것이기 때문에각 사용자가 이동할 때마다 현재 위치에서 연결 가능한 BC를 탐색하고그에 따른 최댓값을 완전 탐색으로 구하는 방식이 효율적이다.각 사용자는 이동할 때마다 현재 위치에서 접근 가능한 BC를 탐색한다.두 사용자가 동시에 접속 가능한 BC 목록을 완탐으로 최대 충전량을 정한다.같은 BC에 접속할 경우해당 BC의 성능을 한번만 더한다 → 균등하게 분배서로 다른 BC에 접속할 경우각 사용자의 충전량을 더해 최대 충전량을 계산한다. ✨ 제출 코드import java.io.BufferedR..

[백준] 17472. 다리 만들기 2 📌 풀이 과정문제를 읽고 풀 엄두가 나지 않는다면 시리즈 1부터 푸는 것을 추천합니다..[백준] 2146. 다리 만들기 이 문제는 여러개의 섬을 다리로 연결해 하나의 연결된 그래프를 만들고, 그 총 다리 길이의 최소값을 찾는 최소 신장 트리(MST) 문제이다. BFS를 통해 각 섬을 구분한 후 섬 사이에 연결 가능한 다리를 계산한다. 최소값이 될 수도 있는 다리들을 우선순위 큐에 저장한 다음, 크루스칼 알고리즘을 통해 MST를 구현해 모든 섬이 하나로 연결되도록 하면 된다. 문제 조건1. 다리의 방향이 바뀌면 안된다. 무조건 가로 or 세로2. 다리의 길이는 2 이상이어야 한다.모든  섬을 연결하는 다리 길이의 최솟값을 구해야 한다. 입력 값에서 섬은 모두 1로 ..

[백준] 17136. 색종이 붙이기 📌 풀이 과정큰 색종이를 먼저 붙이는 것이 효율적이므로큰 색종이로 덮을 수 있는 범위를 줄이고, 남은 작은 영역에 더 작은 색종이를 붙이도록 해야한다.그리고 색종이를 붙이는 과정에서 잘못된 선택일 경우, 다시 돌아와서 더 작은 색종이를 붙이는 로직이 필요하다.즉, 색종이를 붙이는 순서에 따라 최종 결과가 달라지기 때문에 모든 경우를 시도하는 백트래킹이 필요하다. 1️⃣ DFS 탐색(x, y) 좌표에서 색종이를 붙이면서 최소한의 색종이를 찾기 위해 재귀적으로 탐색한다.기저 조건: x >= 10에 도달하면 모든 칸을 탐색한 것이므로, 사용한 색종이 개수(usedPapers)를 최솟값으로 갱신한다.(y >= 10)일 때는 한 행을 다 탐색한 것이므로 다음 행으로 이동한다...