본문 바로가기

BFS12

[백준] 25688: 빠른 무작위 숫자 탐색 - 비트마스크 상태를 포함한 BFS (Java) 문제 바로가기숫자 1부터 6까지 모두 방문해야 한다5 x 5 격자에서 상하좌우로 이동하며 숫자 1부터 6까지 모두 방문하는 최소 이동 횟수를 구해야 한다. -1인 칸은 지나갈 수 없고, 숫자를 방문하는 순서는 정해져 있지 않다.일반적인 격자 최단 거리 문제처럼 좌표만 방문 상태로 사용하려고 했다. 하지만 같은 칸에 도착했더라도 지금까지 방문한 숫자의 집합이 다르면 이후에 해야 할 일이 달라진다.예를 들어 같은 (row, col)에 도착한 두 상태가 다음과 같다고 해보자.현재 좌표방문한 숫자앞으로 방문할 숫자같은 칸1, 23, 4, 5, 6같은 칸1, 32, 4, 5, 6좌표만 같다는 이유로 둘 중 하나를 제거하면 필요한 숫자를 모두 방문하는 경로를 놓칠 수 있다. 따라서 BFS 상태에 현재 위치와 숫자 .. 2024. 5. 17.
[프로그래머스] 미로 탈출 - 레버를 기준으로 BFS 두 번 실행하기 (Java) 문제 바로가기출구보다 레버에 먼저 도착해야 한다미로의 시작 지점 S에서 출구 E까지 이동해야 한다. 하지만 출구는 잠겨 있으므로 레버 L을 먼저 당겨야 탈출할 수 있다.S -> L -> E처음에는 시작점에서 출구까지 한 번의 BFS를 실행하면 된다고 생각했다. 하지만 레버를 당기지 않은 상태에서 출구에 도착하는 경로는 정답이 아니다. 반대로 출구 칸을 먼저 지나더라도 레버를 당긴 뒤 다시 돌아와 탈출할 수 있으므로 E를 벽처럼 막아서도 안 된다.모든 정상 경로는 반드시 레버를 지나므로 전체 경로를 두 구간으로 나눴다.탐색출발목표첫 번째 BFS시작 지점 S레버 L두 번째 BFS레버 L출구 E두 구간의 최단 거리를 각각 구해 더하면 전체 최소 시간이 된다.최소 탈출 시간= S에서 L까지의 최단 거리+ L에서.. 2024. 5. 17.
[백준] 23352: 방탈출 - 모든 출발점에서 BFS로 최장 최단 거리 구하기 (Java) 문제 바로가기두 방 사이의 최단 거리 중 가장 긴 값을 찾는다0이 아닌 칸은 이동할 수 있는 방이고, 0인 칸은 지나갈 수 없다. 상하좌우로 이동할 때 두 방 사이의 최단 거리가 가장 긴 조합을 찾아 시작 방과 도착 방에 적힌 숫자의 합을 출력해야 한다.여기서 구해야 하는 것은 단순한 최장 경로가 아니다. 같은 칸을 반복하지 않는 가장 긴 경로를 찾는 문제가 아니라, 각 방 쌍의 최단 거리 중 최댓값을 찾는 문제다.모든 이동 가능한 방 쌍의 최단 거리 계산-> 가장 긴 최단 거리 선택-> 거리가 같다면 양 끝 숫자의 합이 큰 조합 선택모든 이동 비용이 1인 격자이므로 한 출발점에서 다른 방까지의 최단 거리는 BFS로 구할 수 있다.한 번의 BFS만으로는 모든 방 쌍을 비교할 수 없다처음에는 임의의 방 하.. 2024. 5. 17.
[백준] 19238: 스타트 택시 - 우선순위와 연료를 관리하는 BFS (Java) 문제 바로가기한 승객을 태울 때 두 번의 최단 거리 탐색이 필요하다택시는 벽이 있는 N x N 격자에서 승객을 태우고 목적지까지 이동한다. 한 칸 이동할 때 연료를 1 사용하고, 목적지에 도착하면 승객을 태우고 이동한 거리의 두 배만큼 연료를 충전한다.한 명의 승객을 처리하는 과정은 두 단계로 나뉜다.현재 택시 위치에서 태울 승객을 찾는다.선택한 승객의 출발지에서 목적지까지 이동한다.두 단계 모두 벽을 피한 최단 거리가 필요하므로 BFS를 사용한다. 모든 승객을 처리할 때까지 이 과정을 반복한다.택시 위치 ↓ BFS가장 가까운 승객 선택 ↓ BFS승객의 목적지 도착 ↓연료 충전 후 다음 승객 탐색처음에는 승객을 찾는 BFS에서 발견한 승객을 바로 태우려고 했다. 하지만 같은 거리에 여러 승객이 있으.. 2024. 5. 16.
[백준] 1525: 퍼즐 - 문자열 상태로 탐색하는 BFS (Java) 문제 바로가기퍼즐판 전체가 하나의 상태다3 x 3 퍼즐에서 빈칸 0을 상하좌우로 움직여 다음 배치를 만드는 최소 이동 횟수를 구하는 문제다.1 2 34 5 67 8 0한 번 움직일 때마다 퍼즐판 전체의 배치가 바뀐다. 같은 위치에 0이 있더라도 나머지 숫자의 배치가 다르면 이후 이동 결과도 달라지므로, 0의 좌표만 방문 처리해서는 안 된다.1 2 3 1 2 34 0 5 6 0 47 8 6 7 8 5두 상태는 0의 위치가 같지만 서로 다른 퍼즐이다. 따라서 아홉 칸 전체를 하나의 BFS 상태로 사용해야 한다.2차원 배열을 문자열 하나로 바꾼다퍼즐 상태를 매번 2차원 배열로 복사하면 방문 여부를 비교하기 어렵고 배열 객체도 많이 생긴다. 입력을 행 순서대로 이어 붙여 길이 9의 문자열로 만들.. 2024. 5. 15.
[백준] 14867: 물통 - BFS와 HashSet으로 상태 탐색하기 (Java) 문제 바로가기물의 양 두 개를 하나의 상태로 본다용량이 A와 B인 두 물통을 빈 상태에서 시작해 각각 C와 D만큼 채우는 최소 작업 횟수를 구하는 문제다.한 번의 작업으로 할 수 있는 일은 물통을 가득 채우거나, 모두 비우거나, 한 물통의 물을 다른 물통으로 붓는 것이다. 모든 작업의 비용이 1이므로 상태를 그래프로 표현하면 BFS로 최소 횟수를 구할 수 있다.상태: (첫 번째 물통의 양, 두 번째 물통의 양)시작: (0, 0)목표: (C, D)처음에는 물의 양만 바뀌는 구현 문제처럼 보였다. 실제로는 같은 상태를 반복해서 방문하지 않도록 두 물통의 양을 하나의 방문 단위로 묶는 것이 중요했다.한 상태에서 여섯 가지 작업을 만든다현재 상태를 (a, b)라고 하면 다음 상태는 최대 여섯 개다.작업다음 상태.. 2024. 5. 14.
[백준] 25307: 시루의 백화점 구경 - 다중 시작점 BFS와 최단거리 BFS (Java) 문제 바로가기이동하기 전에 위험한 칸부터 구한다격자에는 빈칸, 기둥, 의자, 마네킹과 시작 위치가 있다. 시작 위치에서 도달할 수 있는 의자까지의 최소 이동 거리를 구해야 한다.이동할 때는 다음 조건을 지켜야 한다.기둥이 있는 칸으로 이동할 수 없다.마네킹과의 맨해튼 거리가 K 이하인 칸을 사용할 수 없다.상하좌우로 한 칸 이동할 때마다 거리 1이 증가한다.출발 지점은 위험 범위에 포함돼도 출발할 수 있다.바로 시작점에서 BFS를 하면 이웃 칸마다 주변 마네킹과의 거리를 다시 검사해야 한다. 마네킹이 많으면 같은 거리 계산을 반복하게 된다.나는 문제를 두 단계로 나눴다.1단계: 모든 마네킹에서 동시에 BFS → 위험한 칸을 미리 표시2단계: 시작 위치에서 BFS → 안전한 칸만 지나.. 2024. 5. 14.
[백준] 2146: 다리 만들기 - 섬 번호 붙이기와 BFS로 최단 다리 구하기 (Java) 문제 바로가기육지끼리 연결돼 있어도 다른 섬을 구분해야 한다지도에서 육지는 1, 바다는 0으로 주어진다. 서로 다른 두 섬을 연결하는 다리 중 길이가 가장 짧은 것을 구해야 한다. 다리 길이는 연결을 위해 지나야 하는 바다 칸 수다.모든 육지가 같은 값 1이라 그대로 탐색하면 도착한 육지가 출발한 섬인지 다른 섬인지 알 수 없다. 나는 먼저 BFS로 연결된 육지에 같은 번호를 붙이고, 그다음 바다를 탐색하며 다른 번호의 섬까지 거리를 구했다.1단계: 연결된 육지를 찾아 섬 번호 부여2단계: 바다를 BFS로 이동하며 다른 섬까지 거리 계산섬 번호는 2부터 시작한다0은 바다, 1은 아직 번호를 붙이지 않은 육지로 남겨 두고, 섬 번호는 2부터 사용했다.지도 값의미0바다1아직 분류하지 않은 육지2 이상분류가 .. 2024. 5. 13.
[백준] 16947: 서울 지하철 2호선 - DFS로 순환선을 찾고 BFS로 거리 구하기 (Java) 문제 바로가기순환선을 먼저 찾아야 거리를 구할 수 있다노선은 하나의 순환선과 그 순환선에 붙은 지선으로 구성된다. 각 역에서 순환선까지의 최소 거리를 출력해야 하며, 순환선에 포함된 역의 거리는 0이다.나는 풀이를 두 단계로 나눴다. 먼저 DFS로 순환선에 속한 역을 표시하고, 표시된 역에서 BFS를 시작해 지선의 거리를 계산했다.DFS: 순환선에 포함된 역 표시 ↓BFS: 순환선에서 지선으로 이동하며 거리 계산순환선을 이루는 역 중 하나만 찾는 것으로는 부족하다. 거리 0인 모든 역을 구분해야 지선을 탐색할 때 순환선 내부를 이동한 거리를 잘못 더하지 않는다.무방향 그래프에서 부모로 돌아가는 간선은 순환이 아니다역 사이 연결은 양방향이므로 인접 리스트에도 두 방향을 저장했다.list.get(a)... 2024. 5. 13.
[백준] 11559: Puyo Puyo - BFS와 중력 시뮬레이션으로 연쇄 계산하기 (Java) 문제 바로가기그룹 개수와 연쇄 횟수를 구분한다같은 색 뿌요가 상하좌우로 4개 이상 연결되면 한꺼번에 사라진다. 빈 공간 위의 뿌요가 아래로 떨어진 뒤 다시 제거가 일어나면 다음 연쇄가 된다.나는 한 라운드를 전체 보드 탐색, 그룹 제거, 중력 적용 순서로 나눴다. 이번 라운드에서 제거가 한 번이라도 발생하면 연쇄를 1 늘리고 다음 라운드를 실행했다.보드 전체에서 제거 가능한 그룹 찾기 ↓제거된 그룹이 없으면 종료 ↓연쇄 1 증가 ↓남은 뿌요를 아래로 이동 ↓다음 라운드 탐색같은 라운드에서 빨간 그룹과 파란 그룹이 함께 사라져도 2연쇄가 아니다. 중력을 적용하기 전 한 번의 제거 단계는 모두 합쳐 1연쇄다.BFS로 같은 색의 연결 요소를 모은다보드를 순회하다가 빈칸이 아닌 위치를 만나.. 2024. 5. 13.

티스토리툴바