BFS36

• 

  [백준/BOJ] 3197번: 백조의 호수 문제 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 해설 예전에 시도했던 문제인데 시간초과가 나서 포기했던 문제이다. 오늘 와서 다시 도전해 봤는데 역시나 어떻게 해야 시간초과를 해결할 수 있을지 감이 잡히지 않아 결국 구글링을 하여 이해를 하였다. 처음에 나는 백조를 움직이고, 물을 녹이고 즉, 2개의 큐만을 사용해 문제를 해결하려 했었다. 이 방법으로는 백조가 계속 모든 맵을 탐험하게 되므로 시간초과가 나게 된.. PS(Problem Solving)/BOJ 2023. 2. 13.

• 

  [백준/BOJ] 17086번: 아기 상어2 문제 https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 www.acmicpc.net 해설 처음에는 0인 모든 지점에서 bfs를 수행시켜 가장 가까운 상어까지의 거리를 구하려고 하였다. 하지만 왠지 모르게 계속해서 답이 아닌 값이 나와 다른 방법으로 접근을 해보자는 생각을 했다. 여기서 생각해낸 것은 각 상어가 있는 지점부터 다른 상어가 있는 지점까지를 구해보자였다. 즉, 모든 상어가 있는 지점을 큐에 넣어준 후 bfs를 수행시키는 것이다. 과정은.. PS(Problem Solving)/BOJ 2023. 1. 3.

• 

  [백준/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.