본문 바로가기
728x90

C++/백준 BFS14

[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++] 백준 말이 되고픈 원숭이(1600), bfs, 반례모음 문제 https://www.acmicpc.net/problem/1600 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다. x x x x 말 x x x x 근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포.. 2023. 8. 16.
[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++] 백준 다리 만들기(2146), BFS, 반례모음 문제 https://www.acmicpc.net/problem/2146 회색은 땅, 하얀색은 바다. 땅간의 연결 가능한 최단거리를 구하시오. 반례모음 5 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 2 5 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 6 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 5 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 2 4 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 4 풀이 풀이가 2가지 있습니다. 1) BFS기반 정석적인 풀이 - 땅의 영.. 2023. 8. 9.
[c++] 백준 빙산(2573), BFS, 반례모음 문제 https://www.acmicpc.net/problem/2573 해마다 위의 그림처럼 빙산이 녹습니다. 숫자를 제외한 빈 공간은 모두 0(바다)으로, 1년이 지나면 인접한 빙산을 녹이는데, 0의 개수만큼 녹습니다. 처음 빙산이 분리될 때, 몇 년이 지났는지를 출력하시오 분리되지 않고 모든 빙산이 녹을 때는 0을 출력. 반례 5 5 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 0 4 4 0 0 0 0 0 3 1 0 0 1 3 0 0 0 0 0 1 5 7 0 0 0 0 0 0 0 0 3 3 2 3 3 0 0 4 0 4 0 3 0 0 0 0 0 4 3 0 0 0 0 0 0 0 0 0 5 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0.. 2023. 8. 7.
[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++] 백준 벽 부수고 이동하기(2206), BFS 문제 https://www.acmicpc.net/problem/2206 NxM 형태의 맵에서, 0은 이동가능, 1은 벽으로 이동 불가. 상하좌우로만 이동가능. 좌측 상단(1,1)에서 우측하단(N,M)까지 이동 가능한 최단 거리 출력. 이동 불가시 -1 출력. 벽을 1 개만 부실 수 있음. 풀이 일반적으로 최단거리 출력은 방문여부 체크가 중요함. (map과 방문여부 체크하는 map_check를 따로 만듬) 이미 방문한 곳은 최단거리가 아니라고 가정하기 때문. 하지만, 이 문제는 벽을 1개 부실 수 있기 때문에 이미 방문한 곳이라도 벽을 부수고 방문했느냐 혹은 부수지 않고 방문 했느냐로 나뉘게 됩니다. 다시 말해, 방문여부 체크를 벽을 1개 부셨을 때와 부수지 않았을 때를 나누어서 생각해야 합니다. 따라서,.. 2023. 7. 29.
[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.
728x90

티스토리툴바