너비우선탐색24

• 

  [백준/BOJ] 1926번: 그림 문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 해설 그림이 그려진 영역의 개수와 가장 큰 영역의 넓이를 출력하는 문제이다. bfs를 통해 문제를 풀 수 있다. 입력을 모두 받고, 2중 반복문을 수행하며 아직 방문하지 않은 1이 찾는다. 이러한 1을 찾았다면, bfs를 수행시켜 그림의 영역을 구한다. 그림의 영역을 구하면서 방문 여부 처리를 해주며 이 칸에 또 방문했을 때 bfs를 수행할 일이 없도록 해준다. 이처럼 아직 방문하지 않은 1을 찾.. PS(Problem Solving)/BOJ 2022. 10. 1.

• 

  [백준/BOJ] 9019번: DSLR 문제 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 해설 bfs를 이용하는 문제이다. 숫자를 관리하는데 있어, 문자열이 아닌 int형으로 계산하였다. bfs를 수행할 때 사요오디는 Queue에는 두가지 정보가 담기게 된다. 현재 숫자와 여태 진행된 명령어 두가지로 저장된다. 즉, Pair(num, command)가 담기게 된다. 초기값으로는 Pair(startNum, "")이 된다. 각 명령어마다 계산하는 방법을 보자. D -> .. PS(Problem Solving)/BOJ 2022. 9. 23.

• 

  [백준/BOJ] 5014번: 스타트링크 문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 해설 bfs를 연습하기에 좋은 문제라고 생각된다. 첨에 방문여부처리할 배열의 크기를 어떻게 정할까 고민을 했었는데, 엘레베이터는 건물의 최고층 이후로는 올라갈 수 없으므로 전체 층수 + 1만큼을 배열의 크기로 저장하면 되는 것이었다. bfs를 수행할 큐에는 현재 층수, 움직인 횟수 정보를 담는다. 현재 층수에서 움직일 수 있는 방법은 2가지가 있다. U버튼을 통해 올라가거나, D버튼을 통해 내려가는 것이.. PS(Problem Solving)/BOJ 2022. 9. 22.

• 

  [백준/BOJ] 2583번: 영역 구하기 문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 해설 bfs를 이용하여 푸는 문제이다. 풀이 과정을 나눠보면 다음과 같다. 주어지는 좌표에 해당하는 영역을 미리 체크해놓는다. 모든 사각형의 체크가 끝났다면, 처음부터 반복문을 실행하며 아직 방문하지 않았으며, 사각형 영역에 해당하지 않는 곳을 찾는다. 아직 방문하지 않았으며, 사각형 영역에 해당하지 않는 곳에 도달했다면, bfs를 수행하여 영역의 총 크기가 얼마인지 구한.. PS(Problem Solving)/BOJ 2022. 9. 18.

• 

  [백준/BOJ] 15644번: 구슬 탈출 3 문제 https://www.acmicpc.net/problem/15644 15644번: 구슬 탈출 3 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 해설 이전 문제인 구슬 탈출 2문제랑의 차이점은 출력에 경로가 추가된 것밖에 없다. 앞부분은 구슬 탈출 2문제랑 같으므로 저 글을 확인하도록 하자. 이제 경로를 추가해야 한다. 데이터 클래스에 경로를 저장할 route라는 변수를 추가해주었다. 이제 움직인 방향에 따라 왼쪽이라면 "L", 오른쪽이라면 "R", 위라면 "U", 아래라면 "D"를 .. PS(Problem Solving)/BOJ 2022. 9. 6.

• 

  [백준/BOJ] 13459번: 구슬 탈출 문제 https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 해설 이전에 구슬 탈출2 문제를 풀고 구슬 탈출1문제도 있을 것 같아 검색해보니 역시나 있었다. 구슬 탈출2 이 글을 보고 오는 것을 추천한다. 이 문제와 구슬 탈출2 문제는 출력에만 차이가 있고, 다를 것이 없다. 구슬 탈출2 문제에서는 빨간 구슬이 탈출하는데 최소 몇 번 움직여야 하는지를 출력하는 것이고, 이 문제는 탈출할 수 있다면 1, 없.. PS(Problem Solving)/BOJ 2022. 9. 5.

• 

  [백준/BOJ] 13460번: 구슬 탈출 2 문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 해설 빨간 구슬과 파란 구슬 두개가 있다. 이 중 10번 이하로 움직여서 빨간 구슬만이 구멍에 들어가게 해야한다. 만약 두 구슬 모두 구명에 빠지는 경우 -1을 출력하게 된다. 처음에는 빨간 구슬을 관리할 큐, 파란 구슬을 관리할 큐 이렇게 두개를 만들어 문제를 해결하려 했다. 하지만 한개의 큐로 모든 정보를 다 담고 하는 것이 더 나을 것 .. PS(Problem Solving)/BOJ 2022. 9. 5.

• 

  [백준/BOJ] 16197번: 두 동전 문제 https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 해설 두 동전 중 하나만 보드에서 떨어트리기까지 최소 몇번을 움직여야 하는지 구해야하는 문제이다. bfs를 이용하여 문제를 해결할 수 있다. bfs를 수행할 때 방문여부를 체크하는데, 이 문제에서는 동전이 2개이며 각각의 (y, x)좌표를 갖고 있으므로 4차원 배열을 이용하여 방문여부배열을 선언해야 한다. 즉, 다음과 같이 선언된다. visited[row][col][row][col] 입력을.. PS(Problem Solving)/BOJ 2022. 9. 2.

• 

  [백준/BOJ] 16928번: 뱀과 사다리 게임 문제 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 해설 총 100개의 칸으로 이루어진 보드판에서 주사위를 굴려 100번째 칸에 도달할 수 있는 최소 횟수를 구하는 문제이다. 문제의 조건으로 100번 칸을 넘어가면 이동할 수 없으므로, 딱 100번째 칸에 도달했을 때의 값을 구해야 한다. 우선 뱀과 사다리 각각 어떠한 칸에 놓여 어떠한 칸으로 입력되는지를 저장해놓기 위해 두 개의 Map을 선언하였.. PS(Problem Solving)/BOJ 2022. 8. 28.

• 

  [백준/BOJ] 1660번: 말이 되고픈 원숭이 문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 해설 출발점에서 도착점까지 움직일 때, 최소로 움직일 수 있는 값을 출력하는 문제로 BFS를 사용하여 문제를 풀 수 있었다. 원숭이는 상하좌우로 움직일 수 있고, k번 이하로 말처럼 움직일 수 있다고 한다. 나는 이를 말이 움직일 수 있는 좌표와 원숭이가 움직일 수 있는 좌표로 각각 저장해주었다. private val monkeyX = intArrayOf(1, -1, 0, 0.. PS(Problem Solving)/BOJ 2022. 8. 26.

• 

  [백준/BOJ] 2636번: 치즈 문제 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 해설 판의 가장자리에는 치즈가 놓여있지 않다고 문제에 나와있다. 즉, (0, 0)의 위치 또는 각 판의 가장자리 어디서든 bfs 혹은 dfs를 이용하여 탐색을 해나가면 안에 공기에 접해있는 치즈만을 녹일 수 있다. 치즈가 전부 녹을 때까지 bfs를 수행해줘야 한다. 따라서 bfs를 한 번만 수행하는 것이 아닌, 모든 치즈가 사라질 때까지 반복을 해야 한다. 이를 알기 위해 bfs를 수행하는 과정에서 1(치즈)이.. PS(Problem Solving)/BOJ 2022. 8. 23.

• 

  [백준/BOJ] 3055번: 탈출 문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 해설 각 맵에 입력되는 정보 당 상태를 보자. D: 비버 굴 .: 빈 공간 *: 물 S: 고슴도치 X: 돌 고슴도치는 비버 굴로 이동해야 하며 물 또는 돌이 있는 공간은 지나갈 수 없다. 또한 물은 1분마다 인접한 칸으로 번져나간다. 즉, BFS를 두번 실행시켜야 한다는 것이다. 우선 각 빈 공간에 물이 몇 분이 지났을 때 차는지를 구하는 BFS를 수행한다. 이 과정이 끝났다면, 몇 분 후에 칸에 물이 .. PS(Problem Solving)/BOJ 2022. 8. 18.