문제 문제 바로가기> BOJ 12851번: 숨바꼭질 2 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 동생을 찾는 가장 빠른 시간이므로 bfs를 이용하였고, 가중치가 같지 않은 경우(걸음과 순간이동은 시간 당 이동할 수 있는 칸 수가 다름)에 속하므로 더 빠르게 찾을 수 있는 경우 큐에 다시 한번 넣어 주었다. #include #include #define MAX 100001 using namespace std; int N, K; int cost[MAX]; void ..

문제 문제 바로가기> BOJ 1963번: 소수 경로 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 두 소수 사이의 변환에 필요한 최소 회수를 구하는 것이므로 bfs를 이용하여 문제를 해결해주었다. #include #include #include #define MAX 10000 using namespace std; struct DATA{int num, cnt;}; int arr[4]; bool visited[MAX]; bool notPrime[MAX]; void eratosthenes(){ for (int a=2..

문제 문제 바로가기> BOJ 6087번: 레이저 통신 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 풀이 한 단계 더 발전한 BFS 느낌이었다. 핵심은 4차원 방문 배열 + Prioirty Queue 이용이다. 💡 최단 거리가 아닌, 최소로 거울을 활용하는 횟수를 구하므로, Priority Queue를 이용하여 가장 적은 거울이 필요한 경우부터 탐색해주었다. 💡 visited[y][x][before_dir][next_dir] : 위치 (y, x) , 이전 방향 before_dir , 다음 방향 ne..

문제 문제 바로가기> SWEA 4193번: 수영대회 결승전 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 우승 경로 (= 가장 빠른 시간 내 도착점) 에 도착해야하므로, BFS를 이용했다! 소용돌이는 2초동안 유지되다가 1초동안 잠잠해지므로, 현재시간 % 3 == 2 인 경우가 소용돌이가 잠잠해지는 경우이다! 소용돌이가 잠잠해지지 않은 경우에는 현재 위치에서 대기해야하므로, 초를 + 1 한 후, 현재 정보를 다시 queue에 넣어 주었다! #include #include #include #define MAX 16 #define EMPTY 0 #define WALL 1 // 섬과 같은 장애물 #define..

문제 문제 바로가기> BOJ 1194번: 달이 차오른다, 가자. 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 풀이 미로를 탈출하는데 드는 이동 횟수의 최솟값을 찾는 것이므로, BFS 키를 가진 상태(2^6 경우 존재)에서의 방문 여부를 체크해줘야 하므로, 비트마스킹을 이용했다. import java.io.*; import java.util.*; public class Main { static final int[] dy = {-1,1,0,0}; static final int[]..

문제 문제 바로가기> BOJ 17836번: 공주님을 구해라! 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 풀이 한 칸을 이동하는데, 1 시간이라는 동일한 가중치가 필요하고, 최단 시간을 찾는 문제이기 때문에 BFS 탐색을 이용한다! 이 때 그람을 획득한 경우와 아직 그람을 획득하지 못한 경우가 있으므로 두 가지 경우에 대해 체크해주기 위해 3차원 cost 배열에 값을 저장해준다. cost[y][x][0] : (y,x)에 도착하는 데 걸린 시간, 그람을 획득하지 못한 상태 cost[y][x][..

문제 문제 바로가기> BOJ 1600번: 말이 되고픈 원숭이 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 bfs + 3차원 배열을 이용해서 풀었다. visitCnt[y][x][k] : 말처럼 이동할 수 있는 기회가 k번 남았을 때, (y, x) 에 도달하는 최소 횟수 import java.io.*; import java.util.*; public class Main { static final int dy[] = {-1, 1, 0, 0, -2, -2, -1, -1, 1, 1, 2, 2}..

문제 문제 바로가기> BOJ 1726번: 로봇 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 풀이 BFS + Priority Queue를 이용해서 문제를 해결했다. 문제 해결에 있어 중요한 점을 몇가지 적어보겠다! 1. 로봇이 어떤 좌표(y, x)에서 방향 d를 바라보고 있는 경우는 유일하다. 즉, 한번만 처리해주고, 다시 처리해줄 필요가 없다. 어떻게 왔든, 그 이후로 펼쳐질 결과는 동일할 것이기 때문! 이를 위해 3차원 visited 배열을 이용해주었다. 즉, visited[y][x][로봇이 바라보고 있는 방향]이..

문제 문제 바로가기> BOJ 1584번: 게임 1584번: 게임 첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 www.acmicpc.net 풀이 BFS 탐색을 진행하되, 안전한 구역인 경우, 그 구역에서 먼저 탐색을 진행해주기 위해 deque 자료구조를 이용했다!! #include #include #define MAX 501 #define DANGER 1 #define DEATH 2 using namespace std; struct DATA { int y, x, lose; }; int N, M; int map[MAX][MAX]; b..

문제 문제 바로가기> BOJ 2636번: 치즈 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 풀이 치즈의 구멍인지, 빈칸인지 확이하기 위해서 4꼭지점에서 BFS 탐색을 시작해 주는게 핵심이다! C++ #include #include #define MAX 101 #define EMPTY 0 #define CHEESE 1 using namespace std; struct POS { int r, c; }; int R, C; int total = 0; int map[MAX][MAX]; bool visited[MAX][MAX..

문제 문제 바로가기> BOJ 17142번: 연구소 3 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 풀이 1. 조합을 구현하여, 바이러스 M개를 활성 상태로 변경 2. BFS를 이용하여 바이러스가 모두 퍼지는 시간을 구하고, ans 값 갱신 * 비활성 바이러스 → 활성화 될 때는 바이러스가 퍼지는 시간으로 계산 x ( = 값 update x ) * 빈 칸에 바이러스가 퍼지는 것은 바이러스를 퍼뜨리는 데 걸린 시간에 영향을 주지만, 비활성화된 바이러스가 있는 곳으로 바이러스가 퍼지는 것은 바이러스를 퍼뜨리는 데 걸린 시..

문제 문제 바로가기> BOJ 16234번: 인구이동 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 문제의 요구사항을 구현해주면 되는 간단한 문제였다. 1. 연합을 구하기 위해 그래프 탐색 (DFS or BFS) 진행 2. 연합의 크기 > 1 인 경우, 인구 이동 연합의 크기 < 1 인경우, break ; 정답 출력 크게 위와 같은 2가지 과정으로 이루어지는데, 연합을 구하기 위해 DFS를 사용했을 때가 BFS를 사용했을 때 보다 시간이 훨씬 줄어들었다. 그 이유를 찾아보니 ... DFS함수..

문제 문제 바로가기> BOJ 2206번: 벽 부수고 이동하기 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 벽을 하나씩 제거 + BFS 하는 경우, O(N^2*M^2)으로 시간 초과가 발생한다. 생각해보면, 어느 지점(y, x)에 도착할 때, 남은 기회가 있거나 or 없거나 둘 중 하나의 상태로 도착할 것이다. 이 점을 이용해서 BFS 탐색을 진행하면, BFS를 한번만 돌려도 문제를 풀수 있다! 추가로, 가중치가 동일할 때 최단 경로를 찾는 문제이므로, 가장 먼저 (N-1, M..

문제 문제 바로가기> BOJ 5014번: 스타트링크 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 BFS를 사용해서 푸는 문제였다! #include #include #define MAX 1000001 using namespace std; int F, S, G, U, D; bool visited[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> F >> S >> G >> U >> D; visited[S] = true; queue q; q.push(..

문제 문제 바로가기> BOJ 16236번: 아기상어 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 문제의 요구사항에 따라 구현해 주면 된다. 설명은 주석으로 자세히 적어 놓았다! 이런 문제는 물고기 먹은 처리, 상어 정보 update 등을 잊지 않고 해주는 게 중요한 것 같다. 문제를 풀 때, 알고 있으면 도움이 되는 개념은 다음과 같다! ✔️ operator 재정의 ✔️ 구조체 정의 ✔️ 그래프 탐색 C++ #include #include #include #define MAX 21 using n..