[BOJ] 2206. 벽 부수고 이동하기 📌 풀이 과정벽이 존재하는 미로에서 (0,0)에서 시작해 (N-1,M-1)까지 이동해야 하며, 이동 중에 벽을 한 번 부수는 것이 허용되는 문제다.BFS 탐색 중, 같은 좌표 (x, y)에 도착했더라도 벽을 부수고 도착했는지부수지 않고 도착했는지를 구분해야 하기 때문에 3차원 방문 배열을 사용해야 한다. 3차원 방문 배열의 사용visited[x][y][0]: 좌표 (x, y)에 벽을 부수지 않고 방문한 상태visited[x][y][1]: 좌표 (x, y)에 벽을 한 번 부수고 방문한 상태 이동 가능한 좌표 탐색벽이 아닌 곳으로 이동다음으로 이동하려는 좌표가 map[nx][ny] = 0 이고, 현재 상태(broke)에 맞는 방문처리가 false라면 해당 좌표로 이..

[BOJ] 17135. 캐슬 디펜스 📌 풀이 과정캐슬 디펜스 문제 조건각 궁수는 공격 범위 내에서 가장 가까운 적을 공격하며, 동일한 거리의 적이 여러 명일 경우 가장 왼쪽의 적을 선택한다.매 턴마다 모든 궁수가 동시에 공격하고, 공격받은 적은 제거된다. 공격 후, 살아남은 적은 한 칸 아래로 이동한다.적이 성에 도달하면 게임에서 제외된다. 문제 설계하기1. 적의 위치를 리스트에 저장해, 공격할 대상을 관리한다.2. 3명의 궁수를 성이 있는 칸에 배치하는 조합을 만든다.3. 배치 완료된 각 궁수의 위치에 대해 가능한 적을 탐색한다.적의 위치와 궁수의 거리 계산 → 맨해튼 거리가장 가까운 적을 찾고, 동일한 거리에 여러 적이 있다면 가장 왼쪽 열에 있는 적을 선택한다.4. 적 제거 및 이동하기궁수들이 선..

[백준] 3055. 탈출 📌 풀이 과정고슴도치(S)가 홍수가 난 티떱숲에서 비버의 굴(D)로 이동할 수 있는 가장 빠른 시간을 구하는 문제다.매 분마다 물을 먼저 확장시켜, 고슴도치가 이동할 수 있는지 확인해야 하기에물의 확장과 고슴도치의 이동을 각각의 큐에서 따로 관리 해야한다. 물의 큐(waterQ)물이 퍼지는 모든 좌표를 저장하고, 매 턴마다 물이 퍼지는 과정을 먼저 처리한다. 고슴도치의 큐(hedgehogQ)고슴도치가 이동하는 모든 좌표를 저장하고, 물이 퍼진 후 그 상태에서 고슴도치가 이동할 수 있는지를 확인한다. 💡 동작 흐름1. 매 턴마다 물이 먼저 확장한다.물의 큐에서 모든 물의 좌표를 하나씩 꺼내서 네 방향으로 확장 시킨다.2. 물 확장 후 고슴도치 이동물이 확장된 후 고슴도치가 갈 ..

[BOJ] 1194. 달이 차오른다, 가자 📌 풀이 과정이 문제도 백준의 1600. 말이 되고픈 원숭이 문제처럼 3차원 방문 배열 아이디어를 떠올려야 한다. 각 좌표에서 민식이가 어떤 키를 가지고 있는지 관리해야 하기 때문에민식이가 열쇠와 문을 사용하는 상태를 관리하려면, 3차원 방문 배열이 필요하다.즉, (x, y) 위치에서 열쇠를 가지고 있는 상태에 따라서로 다른 경로로 이동할 수 있으므로 열쇠 상태를 포함한 방문 체크가 필요하다. visited[x][y][key]로, (x, y) 좌표에서 특정한 key 상태로 방문한 적이 있는지를 기록한다.key 상태는 이진수로 표현하여, 열쇠의 소지 여부를 6비트로 나타낸다. 💡 비트로 키 관리하기문제에서 키는 a, b, c, d, e, f로 총 6개다.6개의..

[BOJ] 1600. 말이 되고픈 원숭이 📌 풀이 과정이 문제의 핵심은 3차원 방문 배열을 사용하는 것이다.BFS 탐색 시 좌표뿐만 아니라 말 찬스 사용 여부를 모두 포함해서 상태 관리를 해야 한다. 💡 BFS에서 상태를 관리하는 방법보통 BFS는 2차원 좌표 (x, y)만을 다룰 때 자주 사용한다. 하지만 이 문제에서처럼 좌표 외에도 말 찬스를 사용한 횟수(chance)와 같은 다른 상태를 포함해야 하는 경우도 있다. 이때 좌표와 chance를 하나의 상태로 묶어서 BFS 탐색을 진행해야 한다.즉, 하나의 상태(state)가 (x, y, chance)로 표현된다. 이 상태에서 chance는 말처럼 이동하는 기회를 사용한 횟수를 나타내며, 같은 좌표 (x, y)라 하더라도 말 찬스를 얼마나 사용했는지..

[백준] 14712. 넴모넴모 (Easy) 📌 풀이 과정주어진 격자판에서 나올 수 있는, “넴모”들이 올라간 칸이2 × 2 사각형을 이루지 않는 모든 배치의 가짓수를 출력해야한다. 각 칸을 순차적으로 선택하거나 선택하지 않으면서 모든 경우의 수를 탐색한다.즉, 각 칸에 두가지 경우가 존재한다.1. 넴모를 놓는 경우 (해당 칸 선택 O)2. 넴모를 놓지 않는 경우 (해당 칸 선택 X) (x, y) 좌표 탐색 중일 때, 이미 선택된 칸(x,y 좌표의 좌상단 3칸)들이2 × 2 사각형이 만들어지는 경우 ➡️ 해당 탐색 칸은 선택하지 않는다.아닌 경우 ➡️ 해당 칸을 선택한 경우와 선택하지 않은 경우 모두에 대해 탐색한다.모든 칸을 탐색했을 때 (cnt == N * M), 경우의 수를 증가키고 종료한다. 💡..

[백준] 14567. 선수과목 [백준] 2623. 음악프로그램 → 헷갈리면 이 문제도 풀어보자!📌 풀이 과정위상정렬 알고리즘 문제!!위상 정렬 구현1. 진입 차수가 0인 정점(시작 정점)를 큐에 모두 넣는다.2. 큐에서 진입 차수가 0인 정점을 꺼내어 자신과 인접한 정점의 간선을 제거한다.     → 인접한 정점의 진입 차수를 1 감소시킨다.3. 간선 제거 후 진입 차수가 0이 된 정점을 큐에 넣는다. ✨ 제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.LinkedList;import java.util.L..