BFS 썸네일형 리스트형 백준 2636 치즈 빡 구현 문제를 잡았다. 2D BFS 문제에서 풀듯이 접근해보자 싶었고, 그 접근이 맞았다. 맵 입력을 받고, 테두리를 돌면서 BFS로 탐색을 한다. 상하좌우 탐색을 하면서 빈 공간을 만나면 그 위치도 큐에 넣는다. 만약 치즈를 만나면 그 부분은 공기와 접촉한 부분이므로 표시를 해둔다. 탐색을 하면서 꼭 visited[][] 배열을 채워주자. 테두리 탐색할때나, 큐 안에서 탐색할 때 visited[][] 로 이미 방문한 곳 처리를 하지 않으면 무한루프가 돌거나 연산 속도가 너무 느려질 가능성이 높다. 한번 모든 테두리에서 BFS 탐색으로 접촉면을 표시해준 다음, 전체 위치를 돌면서 녹는 부분을 제거해주고, 치즈 자리수를 세줬다. 치즈 자리수가 0이 되면 모든 치즈가 없어진 것이므로 탐색 종료! 가장 마지.. 더보기 백준 9328 열쇠 비트마스킹 문제를 푸려고 보는 중, 내가 분명히 풀었던건데 비트마스킹을 쓴 기억이 없어 들고와봤다. 내가 풀었을때는, BFS 탐색을 조금 예외상황을 넣으며 풀었다. 처음 접근할때는, 맵을 곧이곧대로 입력받고 시작 점을 하나 잡아서 구현했었다. 이 경우 벽이 아닌곳을 통해 다른곳으로 이동하는 경우 처리가 너무 빡셌다. 그래서 그냥 맵 주변을 전부 접근가능한 . 로 표시하는 방법을 선택했다. 이 경우, 자연스럽게 BFS탐색으로 해당 케이스가 커버된다. 맵 입력을 받은 뒤, 열쇠 리스트를 입력으로 받아 해당 열쇠로 열 수 있는 문을 전부 갈 수 있는 '.'로 대체해준다. 열쇠 입수 순간에 맵에 표시를 한다는 생각은 차마 못했는데, 다른 솔루션에서 봤다. 입수 키 리스트를 들고, 문을 볼때마다 키 리스트와 대조.. 더보기 백준 10026 적록색약 DFS(깊이 우선 탐색)을 활용하는 문제이다. 2D 맵을 쓰는것을 보고 이건 BFS인가 DFS인가 했는데 경로를 찾는게 아니라 일단 DFS로 생각했고, 그쪽 접근이 나쁘지 않았다. 이전에 MST 문제를 풀 때, 2D로 된 섬들이 있는 맵에서 MST를 찾는 문제가 있었다. 해당 문제에서는, 지도에 섬이 몇개 있는지 알아야 했고, 맵에 있는 각 섬 픽셀이 어느 섬에 속해있는지 찾아야 했다. 그 과정에서 DFS를 사용해 섬 그루핑을 했는데, 그것과 거의 동일하게 이번 문제 풀이가 진행된다. 문제 풀이의 흐름은 다음과 같다. 어떤 특정한 픽셀에서 시작한다. 그 픽셀에서 상하좌우 픽셀을 탐색한다. 넘어온 픽셀이 탐색되지 않은 픽셀이고, 넘어오기 전 픽셀 색과 같으면 탐색 배열에 현재 그룹의 인덱스를 적어둔다. 2.. 더보기 백준 1963 소수 경로 BFS 문제중에 좀 특이하게 맵 탐색이 아닌 다른 공간을 탐색하는 문제이다. 어떤 4자리 소수에서 각 자리수를 바꿔가며 다른 소수로 이동하면서 탐색을 하게 된다. 따라서 일단 소수를 찾아놓고, 각 자리수를 바꾼 숫자가 소수인지 확인해야 한다. 소수를 찾아놓을 땐, 에라토스테네스의 체를 이용해 정해진 범위(10000)까지의 소수를 찾는다. memset(filter, 1, sizeof(filter)); filter[0] = 0; filter[1] = 0; for (int i = 2; i < 10000; i++) { if (filter[i]) { for (int j = 2*i; j < 10000; j+=i) filter[j] = 0; } } 그리고, 탐색을 하는 과정에서 각 자리수를 바꿔야 하므로 조금 더 편.. 더보기 백준 2206 벽 부수고 이동하기 BFS를 사용해 맵을 탐색하는 문제이다. 단순히 출발지에서 도착지까지 탐색하는것에 더해, 우리의 플레이어는 원래는 가지 못하는 벽을 한번 부수고 통과할 수 있다.(이하 슈퍼파워) 이 부분에 있어서 살짝 꼬여진 문제라고 볼 수 있다. 일반 BFS 탐색 코드와 달라지는 점은, visited 배열이 달라진다는것과 큐에 넣을때 두 가지 조건(벽을 부수는 경우, 아닌 경우)을 따져야 한다는 점이다. visited[0 or 1][N][M] 배열은, N*M 크기 맵에서 해당 픽셀을 벽을 부수고 나서 도달하였는가(1), 벽을 부수지 않고 도달하였는가(0)을 의미한다. 해당 visited 배열을 보고, 큐에 넣을 때의 조건을 따진다. 다음 방문 픽셀이 벽이고, 벽을 부술 수 있으며, 벽을 부수고 방문하지 않은 경우 ->.. 더보기 [나만 몰랐던 알고리즘] 2D 맵 BFS Breadth-First-Search. 넓이 우선 탐색이다. 2D 맵 나오고 뭐 최단거리 찾아라 이런 문제에 접근 방식을 잘 모르겠어서 찾아보던 와중, 그런 문제는 BFS로 탐색하면 좋다고 해서 알아보았다. 문제 뿐만이 아니라 2D 맵 탐색에 막연한 두려움을 가지고 있어 한번 정리해 보았다. 맵은 2차원 int 배열로 만든다. 탐색을 할 때, 방문한지 여부를 visited 배열에 저장한다. 이 visited 배열은 문제마다 다를 수 있지만, 대개 map 크기와 같다. BFS 의 탐색 특징은 FIFO(First In First Out)이다. queue를 사용해 방문과정을 탐색한다. 현재 상황이나 위치를 구조체로 정의해두면 편하다. 탐색을 할 때 사용할 4방위(상하좌우)나 8방위(상하좌우, 좌상 우상 좌하 .. 더보기 이전 1 다음
