BFS

[백준 2234] 성곽 (C++)

2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 비트마스킹, BFS [백준 16946] 벽 부수고 이동하기 4 (C++) 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 hyeo-noo.tistory.com 위 문제와 아주 비슷한 방법을 적용해서 풀었다. 차이점은 N과 M의 크기가 현재 문제에서는 50, 50이 최대라서 O(N^2 * M^2)이 가..

[백준 16946] 벽 부수고 이동하기 4 (C++)

16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net BFS 우선 bfs를 수행하면서 연속해서 비어있는 칸의 묶음마다 집합의 번호를 매겨주고 집합의 번호에 따라서 집합의 크기를 저장했다. setMap[][] 배열에는 해당 칸의 집합의 번호를 넣어준다. setcount 변수는 bfs를 수행하는 횟수만큼 집합이 생길 것이므로 bfs가 끝날 때마다 1씩 더해줘서 집합의 번호를 가지고 있는다. setnums[] 배열에는 집합의 번호에 따른 집합의 크기를 저장한다. 집합의 크기는 bfs를 수행할 때마다 ..

[백준 17142] 연구소 3 (C++)

17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net BFS 삼성 SW 기출 BFS 시뮬레이션 문제! M은 최대 10개!! 바이러스도 최대 10개이므로 바이러스를 고를 수 있는 경우의 수는 최대 252개! -> 10C5 연구실의 최대 크기는 50x50 = 2500!! 252 * 2500 하면 약 60만개!! 0.25초 안에 해결하기 충분함! 바이러스를 고를 수 있는 경우의 수를 백트래킹을 통해서 구하고, 바이러스 M개를 고르면 고른 바이러스들을 가지고 bfs를 돌린다! 빈 칸에 도달한 경우에만 답을 갱신한다! -> 가장 마지..

[백준 9019] DSLR (C++)

9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net BFS 이미 찾아 본 숫자라면 que에 넣지않도록해서 최대 10000번만 bfs를 수행하도록 했다. 메모이제이션 안하면 4^n 의 시간복잡도로 시간초과가 난다. D S L R 연산을 조심하자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 5..

[백준 1944] 복제 로봇 C++

1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 최소 스패닝 트리 - MST 현재 로봇이 복제를 거듭하며 열쇠를 찾으러 다니는 이동거리를 가장 작게 해야한다. 전체 이동거리를 가장 작게 해야하므로 다익스트라가 아니라 MST알고리즘을 사용해야 한다는걸 알았다. 입력을 받으면서 시작점과 모든 열쇠들은 정점이 되므로 정점 vector에 넣어준다. 정점들 간의 거리를 BFS를 통해 모두 구하고 간선의 정보를 저장한다. BFS 매번 돌면 자신을 제외하고 시작점을 포함한(M-1+1) M번 ..

[백준 2573] 빙산 C++

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net BFS 현재 맵의 빙산의 개수가 0이 될 때까지 반복문을 수행한다. 물과 접촉한 빙산의 높이를 줄여주는 BFS를 수행한다. 높이가 달라진 빙산들은 임시 맵과 큐에 따로 저장한다. 임시 맵의 정보를 기존 맵으로 복사한다. 임시 큐의 빙산 정보를 기존 큐의 빙산정보로 옮김과 동시에 높이가 달라진 빙산들이 서로 떨어졌는지 확인하는 BFS를 수행한다. 중간에 서로 떨어진 경우에는 현재 year를 출력하고 return 한다. 1 2 3 4 5 6 7 8 9 10 1..

[백준 3055] 탈출 C++

3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS 1. 문제 해결 아이디어 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 위 문제랑 거의 똑같은듯 하다 고슴도치는 물이 곧 차오를 지역으로 가지 못하기 때문에 bfs를 통해서 물을 먼저 채워준다 이때 채워진 물을 nextwater 큐에 넣어준다. 물은 . 부분에만 채워질 수 있다. 물..

[백준 6087] 레이저 통신 C++

6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net BFS 1. 문제 해결 아이디어 처음에 시뮬레이션 문제인가? 생각했는데 그냥 BFS에 조건이 몇 개 추가된 문제였다. 먼저 DP풀듯이 각 칸에 도달하기 위한 최소 거울의 개수를 구해야 겠다는 생각을 했다. 그리고 이미 방문한 칸에 다시 도달할 수 있어야 올바른 최솟값을 구할 수 있다고 깨달았다. 가장 기본적으로, 주어진 W, H 범위 내에서만 움직여야하고, 벽인 경우 que에 넣으면 안된다. que의 초기값이 하나의 점이 아니라 임의의 C에서 4방향으로..

[백준 1238] 파티 C++

1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 1. 문제 해결 아이디어 단순한 다익스트라 문제는 A->B까지 가는 거리의 최단거리를 구하는 것이지만 이 문제는 A->X로가는 최단거리 + X->A로 되돌아오는 최단거리를 구해야 한다. A->X로 가는 최단거리를 구해보자. 정점의 개수가 최대 1000개, 간선의 개수가 최대 10000개 이므로 O(|V||E|) = 10,000,000 이 되어 시간내에 풀 수 있다고 생각했다. 그래서 A->X로 가는 최단거리를 A의 개수만..

[백준 3197] 백조의 호수

3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net BFS 1. 문제 해결 아이디어 2021.07.01 - [Algorithm/BOJ] - [백준 2636] 치즈 C++ [백준 2636] 치즈 C++ 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄 hyeo-noo.tistory.com 백조 문제에서 매일 얼음 표면을 찾고, 얼음을 녹이는..