너비우선탐색18 [Swift][BFS] 백준 2206번 (벽 부수고 이동하기) 요구능력 : BFS && 그리디(?) 코드설명 : 처음에 문제를 읽고나서 벽을 1개 부수는게 어떻게 부숴야 최소값이 나오지..라고 당황했다. 내가 생각한 이 문제에서의 핵심 1. 큐마다 벽을 부쉈는지 안부쉈는지를 체크해준다. bfs로 탐색해주면 어차피 모든곳을 탐색하면서 최단경로를 찾기때문에 1을 부쉈는지 여부만 체크해주고 안부쉈는데 앞에 1이있으면 부수고 큐에 부쉈다는 표시를 해주고 다음거부터 안부수면 된다. 2. 벽을 부수고 방문한것인지 벽을 부수지 않고 방문한것인지를 체크해줘야한다. 저는 이 부분을 생각안하고 풀어서 11%에서 틀렸습니다. 백준 문제해결에서 찾은 반례이다. 6 4 0000 1110 0110 0000 0111 0000 위 예제를 보고 예를 하나 들어보면 맨 처음 시작지점을 (0,0)이.. 2022. 1. 3. [Swift][BFS] 백준 16948번 (데스 나이트) 요구능력 : BFS의 사용 코드설명 : 큐에 저장할 때 좌표와 이동횟수를 함께 저장해줬다. 좌표를 활용하는것이기 때문에 방문여부역시 2차원배열을 사용했다. isChecked는 이동할 수 없는경우에 -1을 출력하기위해 선언하였다. 처음에 큐에 r1, c1이 저장되어있는 arr[0]과 arr[1] 그리고 이동횟수인 0을 넣어준다. 방문처리를 해주고 큐에 있는걸 꺼내준다. 큐에서 꺼내준 r과 c가 r2(arr[2]), c2(arr[3])과 같다면 이동이 끝났으므로 이동횟수인 pop.1을 출력해준다. 그 후 아래에는 문제에 적혀있는데로 최소한의 조건을 만족하면이동할 수 있는 곳으로 이동할 수 있도록 처리해준다. 그리고 isChecked가 그대로 true이면 이동할 수 없는 경우이므로 -1을 출력해준다. 후기 :.. 2021. 12. 14. [Swift][BFS] 백준 16928번 (뱀과 사다리 게임) 요구능력 : 요구조건에 따른 BFS를 잘 설계할 수 있는지 코드설명 : 이 문제는 기본적인 BFS를 이해하고 있으면 간단하게 풀릴것 같지만 조건을 아주 잘 지켜줘야 정답에 통과가된다. 우선 나는 튜플을 이용해서 (현재있는위치, 이동횟수)를 큐에 삽입하는 방식으로 문제를 해결했다. 다른 블로그들보면 딕셔너리 많이 사용하던데 나는 그냥 각각 2차원 배열에 사다리[x, y]와 뱀의 위치[u, v]를 넣어줬다. 그리고 BFS를 통해서 처음시작위치가 1이고 이동횟수는 0이기 때문에 큐에 (1,0)을 넣어주었다. 방문처리도 꼼꼼히 해준다. 그리고 형식적인 BFS의 공식..?같은 느낌으로다가 큐가 비어있지않으면 계속해서 while문을 돌려준다. 그리고 큐니까 맨앞에서 뽑아온다.(pop에 저장) 문제가 100에 도착했.. 2021. 12. 14. [Swift][BFS] 백준 13549번 (숨바꼭질3) 요구능력 : BFS에 대한 이해 코드설명 : 이전단계 문제인 숨바꼭질을 풀고오면 수월하게 풀리는문제이다. 먼저 풀고오는걸 권장하는게아닌 먼저풀고오는게 맞는거같다. 큐에 삽입한다는 말은 움직인다는 말인데, 움직이면 시간계산을 해줘야하므로 움직이는것과 시간계산을 함께 넣어서 큐를 튜플배열로 사용하였다. 순간이동이라는 조건이 추가되서 1초가아닌 0초를 더해야하는것을 제외하고는 숨바꼭질과 문제가 똑같다. queue에서 튜플의 첫번째 요소는 현재 위치, 두번째 요소는 걸리는 시간이다. 후기 : BFS관련 복잡한 문제들을 몇번봐서 이렇게 간단한건 어느정도 풀만한 수준이 된거같다. let nk = readLine()!.split(separator: " ").map{Int(String($0))!} let n = nk[.. 2021. 11. 12. 이전 1 2 3 4 5 다음