BFS28 [BOJ] 17135. 캐슬 디펜스(Python) / DFS + BFS 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net # 1h 58m 소요 사용 알고리즘 : DFS + BFS / 자료구조 : 큐, 최소 힙(우선순위 큐) 오랜만에 이렇게 온갖 알고리즘이 섞인 문제를 풀었다. 장장 2시간여의 긴 여정이었다. 두 번째 푸는 문제라 나름 자신했지만, 처음에 코드 설계하고 다 풀고 디버깅하느라 시간이 좀 걸려서 아쉬웠다.. 한 번에 고려했어야 하는데! 일단 아래 코드는 죽일 적을 최소 힙 큐에 담으면서 가장 높은 우선순위의 적을 뽑아 사용하도록 했다. 시간, 메모리 면에서 매우 오래걸리는 코드라 또.. 2021. 4. 8. [BOJ] 6593. 상범 빌딩(Python) / BFS 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 빌딩의 상태를 3차원 배열로 받아 시작 위치부터 도착 위치까지 최단 거리로 갈 수 있는 경우의 거리를 구함 # 1시간 15분 소요 사용 알고리즘 : BFS 최단 거리 구하기 나의 비루한 코딩실력으로 인해 Input 받는 데만 28분이 걸렸다.. 별것도 아닌 것을.. 혼자 이상하게 생각ㅠ 이후로는 주어진 맵대로 3차원 배열인 것만 다르고 일반적인 BFS 문제와 같이 풀면 된다. Input 받으며 시작 좌표를 저장한다.(sl, sr, sc - 몇 층, 몇 행, 몇 열 순.. 2021. 4. 7. [BOJ] 2151. 거울 설치(Python) / BFS 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 하.. 이 문제는 일주일 동안 나를 괴롭혔기에 더욱 각별하다.. 정말 많이 고민 했는데 답 보기가 너무 자존심 상해서 끝까지 답을 안 보고 혼자 고민했다. 길을 걸을 때나 샤워할 때나 자기 전에나 계속 머릿 속으로 문제 푸는 그런 거.. 다들 경험 있으리라 생각한다. 이틀에 한 번 정도 풀어서 제출하고 틀리고를 반복하다 오늘 뭔가 다시 풀어보자! 해서 풀었는데 역시나 제출하자마자 "틀렸습니다"를 받았다. 질문 게시판에 있는 반례를 모두 넣어보며 내 .. 2021. 4. 5. [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. 이전 1 2 3 4 5 다음
