너비우선탐색14 [BOJ] 16197. 두 동전(Python) / BFS 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성. 어렵지 않은 BFS 문제였다. # 1시간 17분 소요 사용 알고리즘 : BFS 최단 시간 알고리즘 input 받으며 두 동전의 위치 좌표를 받는다.(ar, ac, br, bc) bfs 함수에서 두 동전 좌표를 인자로 받는다. 함수 시작하며 check 라는 두 동전의 위치를 확인하기 위한 4차원 배열을 만든다. 그리고 두 동전의 첫 위치를 0으로 표시하고 큐에 담.. 2021. 4. 4. [BOJ] 4485. 녹색 옷 입은 애가 젤다지?(Python) / BFS 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 골드 4 문제인데 체감은 실버 1정도 되는 어렵지 않은 문제였다. N * N 맵의 (0, 0)위치에서 (N-1, N-1) 위치까지 가는데, 맵에 있는 값들을 더하며 이동한다면 목적지까지 도달하는 최솟값을 구하라. 문제 보자마자 BFS를 떠올렸고, 디버깅 없이 한 번에 코드를 짜서 pass를 받았다. # 30분 소요 사용 알고리즘 : BFS 너비 우선 탐색 일반적인 BFS 함수로, visited를 만들어 해당 위치까지 갈 수 있는 최솟값을 표시하.. 2021. 4. 3. [BOJ] 16954. 움직이는 미로 탈출(Python) / BFS 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 8X8 크기의 맵 왼쪽 하단에서 시작해 오른쪽 상단으로 탈출할 수 있는지 여부를 0과 1로 리턴하는 문제. 이 때, 욱제가 이동 후 맵 내의 벽이 한 칸씩 내려온다. # 1시간 31분 소요 사용 알고리즘 : BFS 너비 우선 탐색 우선, 내가 코드를 다 짜고 90%에서 계속 틀려서 반례를 살폈는데, 욱제는 이동하지 않고 제자리에 있을 수도 있다는 것이다. 즉, 8방향 + 제자리까지 해서 총 9개의 방향 델타 좌표를 탐색해야한다는 것! 벽이 움직이는 것은.. 2021. 4. 3. [BOJ] 16509. 장군(Python) / BFS 16509번: 장군 오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해 www.acmicpc.net 10×9 크기의 장기판 위에 상과 왕의 처음 위치가 주어졌을 때, 상이 왕에게 도달할 수 있는 최소 이동 횟수 구하기 단, 이동 중 기물 있다면 해당 방향으로 이동하지 못한다. # 55분 소요 사용 알고리즘 : BFS 최단 거리 구하기 문제 그리기 전에 상이 갈 수 있는 8방향 델타 좌표(dr, dc), 위치별 장애물 좌표(obstacle)를 만들어뒀다. bfs에서 상의 첫 위치를 0으로 표현하고 큐에 담는다. 큐에서 꺼낸 위치에서 8방향 중 갈 수 있는 곳을 모두 boa.. 2021. 4. 2. [BOJ] 12851. 숨바꼭질 2(Python) / BFS 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 해당 번호까지 갈 수 있는 최소 시간과 그 시간에 갈 수 있는 방법은 몇 가지인지 추가적으로 구하는 문제이다! 예전에 숨바꼭질 1 풀었던 문제와 비슷하게 접근했는데, 추가로 구해야 하는 가짓 수 때문에 좀더 머리를 썼다. 사용 알고리즘 : BFS 최단 경로 알고리즘 먼저, K가 N보다 작거나 같다면 -1로 계속 가는 방법 뿐이다. 그러므로 N-K와 1가지 방법을 출력한다. 그렇지 않다면 bfs 함수를 실행해 최소 시간과 경우의.. 2021. 4. 1. [BOJ] 9019. DSLR(Python) / BFS www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 처음에는 DFS로 접근했다가 그렇게 해서는 답도 없을 것 같아서 BFS를 떠올렸는데, 결국 혼자 힘으로 못 풀고 다른 사람의 풀이를 봤다ㅠㅠ 사용 알고리즘 : BFS(최단거리 알고리즘) 여러 설명보다 아래 코드를 보면 이해할 수 있을 것이다. 4자리 숫자이므로 일차원 배열 visited를 10000 크기로 만든다. while문을 돌 때마다 현재 temp에 D, S, L, R 연산을 해주며 큐에 (연.. 2021. 3. 25. 이전 1 2 3 다음
