너비우선탐색18 [Swift][BFS] 백준 7562번 (나이트의 이동) 요구능력 : BFS에 대한 이해 코드설명 : 문제를 읽어보면 움직이려는 칸의 이미지를 보면 BFS로 찾으라는거 같고, 최소 몇번만에 이동할 수 있는지라는 지문에서 BFS임을 확신했다. 그래서 조건을 찾아보면 1. 체스판의 각 칸은 두 수의 쌍 {0 ~ l-1 } * {0 ~ l-1} 2. 한번에 이동할 수 있는 칸 다른 BFS문제들과 마찬가지로 최소값을 찾기위해서는 반드시 방문처리를 해줘야하고 queue를 이용하여 문제를 풀었다. queue를 3가지 튜플로 구성했다. 1번째는 현재있는 칸의 x좌표, 2번째는 현재있는 칸의 y좌표, 3번째는 이동횟수 방문횟수는 어차피 체스판의 최대가 300 * 300이기 때문에 300개씩 잡아줬다. 그리고 이 문제에서 다른 BFS문제들과 차별점은 테스트케이스로 여러번 돌려.. 2021. 11. 12. [Swift][BFS] 백준 14226번 (이모티콘) 요구능력 : BFS에 대한 이해와 응용 코드설명 : 이 문제에서 가장 중요한건 조건을 보고 핵심을 캐치하는것이다. 내가 생각했을 때 핵심은 화면, 클립보드, 시간을 구성해서 큐와 visited배열을 짜는것이다.(조건은 문제를 잘 읽어보면 생각나기때문) 화면, 클립보드, 시간이 함께 움직이기(?) 때문에 하나의 튜플로 정의했다. pop.0은 화면 pop.1은 클립보드 pop.2는 시간을 의미한다. 일반적으로 BFS에서 같은곳을 두번이상 방문하면 최단시간, 최단경로가 나오지 않으므로 방문처리를 해주는데, 방문여부를 표시하는 visited는 visited[1][0]이면 화면에 1개있고 클립보드가 0개있을 때 라는 의미이다. 이렇게 해준이유는 화면개수와 클립보드개수에 따라 다음번에 while문을 돌때 시간에 영.. 2021. 11. 11. 이전 1 2 3 4 5 다음