본문 바로가기
728x90

BFS9

[c++] 백준 벽 부수고 이동하기 3(16933), bfs, 반례모음 문제 https://www.acmicpc.net/problem/16933 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 이동하지 않고 같은 칸에 머물러있는 경우도 가능하다. 이 경우도 방문한 칸의 개수가 하나 늘어나는 것으로 생각해야 한다. 이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 .. 2023. 8. 22.
[c++] 백준 벽 부수고 이동하기 2(14442), bfs, 반례모음 문제 https://www.acmicpc.net/problem/14442 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다. 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오. 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤.. 2023. 8. 21.
[c++] 백준 숨바꼭질 4(13913), bfs, 반례모음 문제 https://www.acmicpc.net/problem/13913 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다. 반례모음 24 300 10 24 2.. 2023. 8. 18.
[c++] 백준 숨바꼭질 3(13549), bfs, 반례모음 문제 https://www.acmicpc.net/problem/13549 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 반례모음 10000 0 10000 2 7 1 1 17 1 4 6 1 0 1 1 0 3 2 0 0 0 1 32 0 3 22 1 5 7 2 1 10000 3 1.. 2023. 8. 16.
[c++] 백준 텀프로젝트(9466), BFS, 반례추가 문제 https://www.acmicpc.net/problem/9466 팀을 이루지 못하는 학생 수 구하기. 팀을 이루는 조건 1 -> 3 -> 5 -> 1 : 자기 자신으로 돌아와야 함. 1 -> 1 : 혼자 팀 팀을 못 이루는 조건 1 -> 3 -> 5 -> 3 : 1은 팀 x 1 -> 3 -> 5 -> 5 : 1,3은 팀 x 풀이 위의 조건에서와 같이 현재 n에서 탐색을 할 때, 팀을 이루든 이루지 못하든 무조건 순환루프에 걸리게 되어 있습니다. 순환루프에 걸렸을 때, 팀을 이루는 사람과 이루지 못하는 사람을 분리해서 표시를 해주면 됩니다. n번째에서 표시를 마치고, n+1번째에서 탐색을 할 시, 1~n번째에서 표시한 사람을 가르킨다면 이 또한 팀을 이루지 못한다고 할 수 있습니다. 이미 앞에서는 .. 2023. 8. 1.
[c++] 백준 숨바꼭질(1679), BFS, 반례모음 문제 https://www.acmicpc.net/problem/1697 수빈이(N)이 동생(K)를 찾는 가장 빠른 시간 출력 수빈이는 현재 위치(X)에서 3가지 동작(X+1, X-1, 2*X) 가능 5 17 -> 4출력(5-10-9-18-17) 풀이 1차원에서 수빈이의 이동 가능한 모든 방향을 탐색, 동생을 찾을 때까지 계속한다. 마치 가능한 모든 경우의 수를 탐색하는 것과 같음. 1차원 벡터(배열)의 map을 만들고, 수빈이의 시작지점에 1의 값을 넣고, 다음 이동 배열 값에 현재 위치의 값+1을 해주며 확산한다. 동생을 찾을 시 종료. 예외 처리 - 이전에 방문한 좌표는 패스 - 배열의 일정 크기를 넘으면 패스 - 0 0을 받을시 0을 출력 - 기타 반례모음 아래에. 반례모음 입력 6 11 정답 (6.. 2023. 7. 26.
[c++] 백준 불!(4179), BFS, 반례모음 문제 https://www.acmicpc.net/problem/4179 J와 F(불)이 미로에 있음. J는 F를 피해 미로를 빠져나와야 한다. 미로 밖으로 나오면 성공 #: 벽 .: 지나갈 수 있는 공간 J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간) F: 불이 난 공간 J가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다. J가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 풀이 맵에서의 J와 F의 좌표를 모두 큐에 쌓고, 하나씩 BFS를 이용해 인접한 좌표로 이동한다. 핵심은 조건문을 통한 예외처리가 아닐까 싶다. 특이사항 - 불이 여러개일 수 있음. - J가 벽에 갇힐 수도 있음. 맵을 문자열로 구성하고, J나 F가 이동시에 현재 좌표에.. 2023. 7. 26.
[c++] 백준 토마토(7576), BFS, 반례모음 문제 https://www.acmicpc.net/problem/7576 격자 모양에 안익은 토마토와 익은 토마토가 존재 익은 토마토는 하루가 지날 때마다 인접한 안익은 토마토를 익게 만듬 모든 토마토를 익게 만드는데 걸리는 날짜는? 반례모음 2 2 1 1 1 1 0 5 3 0 -1 0 0 0 -1 -1 0 1 1 0 0 0 1 1 -1 2 2 -1 0 0 1 1 3 3 1 0 0 0 0 -1 0 -1 0 -1 3 3 0 0 1 0 0 1 0 0 1 2 3 3 -1 0 -1 0 1 0 -1 0 0 2 풀이 익은 토마토들 각각으로부터 BFS를 수행해 인접한 토마토를 익게 만든다. 마치 멀티 프로세스처럼 하루마다 동시에 수행하는 것처럼 보임 그러나, 이는 현재 익은 토마토의 위치 정보들을 큐에 쌓아서 순차적으.. 2023. 7. 26.
[c++] 백준 그림 (1926), BFS 문제 https://www.acmicpc.net/problem/1926 입력 그리드와 1과 0으로 이루어진 값들을 받고, 1로 이어진 도형 개수와 최대 크기를 출력하는 문제. 도형은 상하좌우로만 이어질 수 있음. 풀이 BFS 알고리즘을 기반으로 모든 그리드의 좌표들에서 도형을 찾으면 됨 코드 알게 된 점 BFS 알고리즘 git 코드 https://github.com/intlabSeJun/c-plus-coding-test/blob/master/9.%20BFS/%EA%B7%B8%EB%A6%BC(1926).cpp 2023. 7. 24.
728x90

티스토리툴바