bfs28 [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][DFS][LV_2][프로그래머스] 배달 요구능력 : DFS에 대한 이해 코드설명 : 주의: 이 해설은 32번 케이스를 통과하지 못했습니다. DFS로는 도저히 32번을 통과못할것 같지만 풀이가 궁금하신 분들이 계실것같아 올렸습니다. 다음번에 BFS로 풀어보고 따로 글 올리겠습니다. 간선과 가중치가 주어진 문제로 연결그래프를 만들고 그 그래프를 타고가는 방식으로 코드를 짜면된다. 1. 연결그래프 작성 주어진 간선과 가중치를 튜플을 이용해서 연결그래프에 함께 담았다. for i in 0.. k { return } if !visited[i.0]{ visited[i.0] = true count += i.1 if count Int { var visited = Array(repeating: false, count: N + 1) var result = Se.. 2021. 11. 18. [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. 이전 1 2 3 4 5 6 7 다음
