백준177 [Swift][BFS] 백준 1261번 (알고스팟) 요구능력 : BFS에 대한 이해 코드설명 : 이 문제를 푸는 방법은 여러가지가 있겠지만, 저는 BFS에서 가중치를 이용해서 문제를 풀었습니다. 아래는 이 문제에서의 핵심코드입니다.(제가 생각하기에..) arr배열은 입력받은 배열로 1이면 벽, 0이면 뚫려있는공간을 의미합니다. dist배열은 미리 모두 Int.max값으로 초기화 해놨는데, 그 이유는 비교해서 가중치 값을 작은값으로 치환하기 위해서입니다. 아래에서 어떤느낌으로 가중치가 가중되는지 그림으로 그려봤습니다. if arr[nx][ny] == 1{ if dist[nx][ny] > dist[pop.0][pop.1] + 1{ dist[nx][ny] = dist[pop.0][pop.1] + 1 queue.append((nx, ny)) } }else if .. 2021. 11. 15. [Swift][DP] 백준 11054번 (가장 긴 바이토닉 부분 수열) 요구능력 : DP에 대한 이해 코드설명 : 바이토닉 부분수열을 오해하고 문제를 풀었다. 증가하다가 가운데가 가장크고 점점 작아지는 수가 나오는줄알고 처음에는 증가하는 부분수열 + 인덱스저장 + 감소하는 부분수열로 풀었는데, 생각보다 간단하게 풀리는 문제였다. 이론적인 부분은 https://st-lab.tistory.com/136 엄청 잘 정리해 놓으셨다. 우선 가장 긴 증가하는 부분수열 dp를 구하고, 가장 긴 감소하는 부분수열 dp를 구해준다. 그리고 두 dp의 각 인덱스를 합쳐주고 1씩 빼주면 그게 두 수열을 합친것이다. 그래서 점점 작아지는 부분과 점점 커지는 부분이 합쳐져서 바이토닉 수열이된다. 내가 이해가 안갔던 부분을 위주로 설명하자면, 두 개를 합친다고 어떻게 하나의 바이토닉 수열이 되는가?.. 2021. 11. 15. [Swift][BFS] 백준 13549번 (숨바꼭질3) 요구능력 : BFS에 대한 이해 코드설명 : 이전단계 문제인 숨바꼭질을 풀고오면 수월하게 풀리는문제이다. 먼저 풀고오는걸 권장하는게아닌 먼저풀고오는게 맞는거같다. 큐에 삽입한다는 말은 움직인다는 말인데, 움직이면 시간계산을 해줘야하므로 움직이는것과 시간계산을 함께 넣어서 큐를 튜플배열로 사용하였다. 순간이동이라는 조건이 추가되서 1초가아닌 0초를 더해야하는것을 제외하고는 숨바꼭질과 문제가 똑같다. queue에서 튜플의 첫번째 요소는 현재 위치, 두번째 요소는 걸리는 시간이다. 후기 : BFS관련 복잡한 문제들을 몇번봐서 이렇게 간단한건 어느정도 풀만한 수준이 된거같다. let nk = readLine()!.split(separator: " ").map{Int(String($0))!} let n = nk[.. 2021. 11. 12. [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. 이전 1 ··· 17 18 19 20 21 22 23 ··· 45 다음
