본문 바로가기

BFS18

[백준/C++] 벌집들 (No. 3805) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 문제 이해를 잘 해야 풀 수 있는 문제였다. 문제를 잘 보면 벌집이 있는 곳들 사이의 경로만 존재하며, 그 경로들 중 하나가 무작위로 문제가 발생한다는 것을 알 수 있다. 즉, (벌집O, 벌집X)인 나무들 사이에는 경로가 없고 오로지 (벌집O, 벌집O)인 나무들 사이에만 경로가 있다는 뜻이다. 여기서 무작위로 하나의 경로에 문제가 생겨도 모든 나무들 사이를 이동해야한다. 이러한 조건을 만족하기 위해서는 내가 벌집을 만든 나무들간의 경로가 사이클을 이루어야 한다는 것을 알 수 있다.(만약 사이클이 아니면 오로지 하나의 경로만 있는 벌집의 경로를 파괴하면 다른 벌집으로 못가는 경우가 생기게 됨).. 2024. 12. 25.

[백준/C++] 하이퍼 토마토 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 사실 BFS를 풀 줄 알면 쉽게 해결할 수 있는 문제다.하지만, 11차원이라는 점에서 그렇게 되면 거의 반 노가다 문제가 된다. 그래서 어떻게 하면 코드를 효율적으로 짤 수 있을까? 생각을 하다가, 1차원 배열로 토마토들을 배치한 뒤 인접 이동을 +1,-1이 아니라 n칸씩 이동하면 되겠다는 생각이 들었다. 간단한 예를 생각해 보자만약 차원이 [3 2 2 1 1 1 1 1 1 1 1]로 주어진다면 토마토를 이렇게 표현할 수 있다.파란색으로 표시된 부분은 2번 토마토가 다른 토마토를 익게 할 수 있는 범위다. 즉.. 2024. 5. 26.

[백준/C++] 여행 가자 (No. 1976) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 경로가 서로 연결된 상태인지 구하는 문제다.왜냐하면 여러 경로가 주어지고, 그 경로를 따라 이동할 수 있는지 묻는 문제기 때문이다. 그래서 Union Find로 분류된 문제지만, 단순한 BFS로 풀 수 있다. 간단히 BFS로 푸는 방법을 설명하자면, 주어진 경로에 있는 위치에서 탐색을 시작한다.그리고 방문한 노드들을 기록할 배열 visited를 만든 뒤 방문한 위치는 true로 바꿔준다. 이제 주어진 경로를 탐색하며 한번이라도 방문하지 않은 노드가 있다면, NO를 출력하면 된다. 즉, 문제를 요약하면 특.. 2024. 5. 25.

[백준/C++] DSLR 문제 문제 설명 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 이전에 풀었던 문제들과 큰 차이가 없는 문제다.가장 적은 연산으로 특정 수를 만드는 것을 목표로 하기 때문에 BFS로 풀 수 있다. BFS로 구할 경우 어떤 수 A를 DSLR 연산으로 다른 수 k를 만들 수 있고 이 때, k가 처음 나온다면, k가 나오는 가장 빠른 방법이 되기 때문이다. 그러므로 배열을 이용해 어떤 수A를 연산해 k를 처음 만들었을 경우에 어떤 연산으로 k가 되었는지를 array[k]에 저장한다.그리고 A에서 k로 변했다고 저장하기 위해 arrayIdx[k]에 A를 저장한다. (어떤 수에.. 2024. 5. 12.

[백준/C++] 숨바꼭질 4 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 예전에 풀었던 숨바꼭질와 거의 다를게 없는 문제다." data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 이동 시간이 항상 같으므로 BFS로 탐색을 시작해 첫 방문하는 경우가 항상 이동 시간이 가장 작다는 것을 알 수 있다. 여기서 다른 점은 어떤 경로로 이동을 했는지 출력도 해야한다. 그러므로 visited 배열을 만든 뒤 첫 방문을 할 경우 어떤 위치에서 이동했는지 저장을 한다면, 역으로 어떤 경로를 통해 왔는지도 쉽게 구할 수 있다. [아이디어 정리]이동 시간이 항상 같으므.. 2024. 5. 11.

[프로그래머스/C++] 카카오프렌즈 컬러링북 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 DFS나 BFS로 연결된 영역을 탐색하고, 그 크기를 계산하면 쉽게 풀 수 있는 문제다. 문제에서 구해야하는 값이 영역의 개수, 그리고 영역 중 가장 크기가 큰 영역이다. 그렇기 때문에 영역을 만나면 그 영역의 수를 세고 방문했다는 표시를 한다.(다시 탐색을 하지 않도록 표시를 해야한다) 연결된 부분 즉, 모든 영역을 탐색했다면 영역의 개수를 1 추가하고 최대영역의 크기와 비교한다. 만약 이번에 탐색한 영역의 크기가 이전에 저장된 가장 큰 영역의 크기보다 크다면 값을 갱신하면 된다. 마지막으로 구한 영역의 수.. 2024. 4. 28.

[백준/C++] 벽 부수고 이동하기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 (0, 0)에서 출발해 (N-1, M-1)에 가장 빨리 도착하는 최단경로를 구하는 문제다. 이 문제에서 중요한 점은 경로 중간에 벽이 있는 경우에는 벽을 부수고 이동할 수 있다는 점이다. 일단, 최단경로를 구하기 위해서는 BFS를 이용해 특정 지점에 처음 도달했을 경우에 이동한 칸수가 정답이다. 하지만 이 문제에서는 벽을 부술 수 있기 때문에 이를 고려해야 한다. 그러므로 특정 지점에 방문했을 때, 벽을 부수고 방문했는지와 벽을 부수지 않고 방문했는지를 구분해서 저장해 준다. 이를 위해 visited의 2차원 vector에 벽을 부수고 방문한 경우, 부수지 않고 방문하는 경우의 2가지 경우를 고려해 [.. 2024. 4. 13.

[백준/C++] 뱀과 사다리 게임 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 칸에 이동했을 때, 뱀이나 사다리가 있다면 다른 칸으로 이동할 수 있는 게 특징이다. 이렇게 이동을 하면서 마지막 칸인 100번 칸에 도착하면 승리하는데, 주사위를 조작해 원하는 숫자를 낼 수 있다면 100번 칸에 도달하기 위해 주사위를 가장 적게 굴리는 횟수를 구하는 문제다. 한번 이동할 때 마다 주사위를 굴리는 횟수가 1씩 늘어나므로, BFS로 문제를 풀면 빠르게 풀 수 있다. 이동 할 수 있는 곳은 현재 칸에서 1~6으로 6 곳이고, 이 6곳에 도착했을 때 뱀이나 사다리가 있다면 다른 칸으로 이동하면 된다. 이렇게 BFS로 문제를 구현하면 100번 칸에 처음 도달했을 때, 주사위를 굴린 횟수.. 2024. 4. 13.

[백준/C++] 3차원 토마토 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 토마토의 3차원 버전이다. 모든 토마토가 익을 수 있는지 확인하고, 만약 모든 토마토가 익는다면 걸리는 최소 시간을 구하는 문제다. 특정위치에 있는 토마토가 익을 수 있는 시간 중 가장 빠른 시간을 구해야 하므로, BFS를 이용하면 첫 방문했을 때가 토마토가 가장 빨리 익는 시간이 되는 것이다. 여기서 특정위치에 있는 토마토가 다음으로 탐색할 수 있는 곳은 6방향이다. 이를 이용해 6방향으로 탐색을 하고, 방문한 적이 없으면서 토마토가 있으면 queue에 넣어 탐색을 진행하면 된다. BFS로 문제를 풀 줄 안다면, 처음부터 토마토가 없는 빈칸만 잘 구분해주면 된다. 모든 위치에 대해 탐색이 끝났다면, .. 2024. 4. 12.

[백준/C++] 숨바꼭질 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 N에서 출발해 M에 도착하는데 걸리는 가장 적게 걸리는 시간을 구하는 문제다. 그러므로 BFS로 풀면 M에 처음 도달한 순간이 가장 시간이 적게 걸린 것이다. 임의의 점 X에서 다음에 갈 수 있는 곳은 X+1, X-1, X*2이다. 그러므로 이 3곳에 대해 queue에 삽입해 탐색을 하면 된다. 여기서 다음에 갈 위치가 이미 방문한 적이 있다면, queue에 삽입할 필요가 없다. 왜냐하면 BFS로 탐색을 하기 때문에 첫 방문이 가장 시간이 적게 걸린 순간이기 때문이다. 이제 문제를 풀 때, 방문을 체크할 visited vector와 queue를 이용해 문제를 풀면 된다, [아이디어 정리] N에서 M.. 2024. 4. 12.

[프로그래머스/C++] 튜브의 소개팅 (2017 카카오코드 본선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 보고 어떤 값을 기준으로 priority_queue를 사용하거나 BFS로 풀면 되겠다는 생각이들었다. 그런데 priority_queue를 사용하면 정렬하는데 시간이 걸린다. 게다가 내가 return 할 답은 거리가 가장 짧은 값 중에서 대화시간이 가장 짧은 값이기 때문에 거리를 기준으로 정렬을 할 것이라면, BFS를 이용하면 된다. 그래서 BFS로 문제를 풀었다. BFS를 이용하면 항상 원점에서 이동한 거리가 짧은 값이 queue에서 먼저 나온다. 그러므로 이를 이용해 특정 지점에 방문할 때 마다 가지치기를 해, 쓸모없는 경우들을 가지치기 해 주었다. 가지치기를 하기 위해서 visited라는 2차원 배.. 2024. 3. 28.

[프로그래머스/C++] 블록 이동하기 (2020 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 풀이만 생각하면 그렇게 어렵지 않은 문제다. 가장 빠르게 도달하는 방법을 찾는 문제이므로, BFS로 문제를 해결하면 된다. 4방향으로 이동하는 경우와, 회전하는 경우를 고려하면 되는데, 문제는 회전을 구현하는게 생각보다 힘들었다. 푸는 방법은 로봇이 가로일 경우, 세로일 경우가 있으므로 visitedHorizontal, visitedVertical 두 2차원 벡터를 이용해 이미 방문 한적이 있는지를 판단하고, 방문했다면 Queue에 넣지 않기로 했다. 여기서 일반적인 이동은 Horizontal 방향이면 visitedHorizontal에서 방문한 적이 있는지 확인하면 되는데, 회전할 경우 Horizont.. 2024. 2. 8.

[프로그래머스/C++] 등대 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 주의해야하는 점이 A와 B 등대가 있다면 두 등대 중에 한 등대는 무조건 켜져있어야 한다는 점이다. 위 그림과 같이 등대가 켜져 있어도, A와 B 등대 사이에 불이 켜져있지 않기 때문에 정답이 될 수 없다. A와 B 등대중 하나가 켜져있어야 된다. 이제 문제를 풀때 사이클이 없으므로 하나의 트리로 볼 수 있다. 이를 이용해 1을 트리의 최상단 노드라고 가정하고, leaf 노드를 찾는다. 여기서 leaf 노드를 찾을 경우 leaf 노드의 불을 켜는 것 보다 부모 노드의 불을 켜는게 더 좋다. 왜냐하면 leaf 노드는 연결된 노드가 하나이고, leaf 노드의 부모 노드는 최상단 노드인 1을 제외하면 연결된.. 2024. 2. 7.

[프로그래머스/C++] 부대복귀 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에 문제를 보고 시작 부대를 기준으로 BFS를 각각 실행하는 문제라고 생각했다가, 어떻게 반복 횟수를 줄일 수 있을까 생각하다보니 모든 부대의 destination이 동일한 게 눈에 보였다. 반대로 말하면 destination에서 BFS로 갈 수 있는 모든 부대를 탐색한다면 한번의 BFS로 문제를 해결할 수 있다. 또한 roads에서 [a, b]가 주어지면 [b, a]가 주어지지 않듯이 중복된 정보는 주어지지 않는다고 했다. 그러므로 각 부대에서 방문할 수 있는 다른 부대 정보를 2차원 vector에 push해서 저장하면 반복의 횟수도 줄어들게 된다. [아이디어 정리] roads의 정보를 바탕으로 방문할 .. 2024. 1. 24.

[프로그래머스/C++] 지형 이동 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때 어떻게 풀지 고민했다. 처음에는 특정 사다리를 놓을 경우 최소값만 구하려고 했는데, 그렇게 풀면 최소값을 구하는 과정에서 A, B, C 지역이 전부 연결되어야하는데 B, C지역끼리만 연결되는 경우가 생기기 때문이였다. 그래서 BFS로 사다리가 없는 지역들을 구분하고, 구분된 지역에서 다른지역으로 갈 때 사다리를 최소로 놓도록 했다. 문제를 풀다보니 모든 지역을 잇기 위해 사다리를 놓는 비용의 합이 최소가 되어야 했기 때문에 이는 MST 문제와 같은 문제라는 것을 알았다. 그래서 가장 비용이 적게 드는 사다리를 놓은 다음에, 사다리를 놓아서 새롭게 갈 수 있는 지역이 생기면 그 지역에서 사.. 2024. 1. 18.

이전 1 2 다음

티스토리툴바