bfs28 [Swift][BFS] 백준 2178번 (미로탐색) 요구능력 : BFS에 대한 이해 코드설명 : 최소의 이동을 요구하는 문제는 BFS로 접근하는게 맞는것같다. DFS로도 풀 수는 있지만 DFS는 모든 경우의수를 다 돌아보기 때문에 자칫하면 시간초과가 날 수 있다. 이 문제는 문제에서 최소의 이동을 요구했기 때문에 BFS로 풀어볼 것이다. 1. n,m 과 좌표의 크기 받기 let nm = readLine()!.split(separator: " ").map{Int(String($0))!} let (n, m) = (nm[0], nm[1]) var arr = [[Int]]() for _ in 0..= m {continue}// nx와 ny가 배열밖으로 넘어가는것을 방지 if arr[nx][ny] == 0 {continue} //1일때만 이동가능하기 때문에 0일떄.. 2021. 10. 8. [Swift][BFS] 백준 13913번 (숨바꼭질 4) 요구능력 : BFS에 대한 이해 코드설명 : "이게틀려?" 를 많이 시전한 문제이다. 이 문제를 풀기전에 숨바꼭질부터 풀고오자. 숨바꼭질에서 달라진점은 지나온경로를 찾는것이다. 지나온경로는 코드에서 visited배열에 저장해줬다. 방문처리와 동시에 경로를 저장했다. 이렇게 안해주고 배열을 따로 추가하면 메모리초과가난다. 경로추가하는 부분은 아래 주석처리를 해두었다. 1. 메모리초과 => 크기가 100001인 배열 3개를 만들어서 메모리초과가 났다. => 아, 참고로 경로를 찾기위한 배열(아래코드에선 visited)에 초기값을 0으로 세팅하면 당연히 메모리 초과가 난다. => 이유는 2 * x에 0이들어가면 0인걸 참고하면 된다. 2. 컴파일에러 처음에 n을 방문처리해줬는데, 방문처리를 하면 코드가 꼬이게.. 2021. 10. 2. [Swift][BFS] 백준 1697번 (숨바꼭질) 요구능력 : BFS에 대한 이해 코드설명 : 왜 BFS로 풀어야되는지에 대한 설명이 아주 잘나와있다.https://chanhuiseok.github.io/posts/baek-14/ [백준] 1697번 - 숨바꼭질 컴퓨터/IT/알고리즘 정리 블로그 chanhuiseok.github.io 스위프트의 경우에는 큐를 구현해줘야하기 때문에 필요한 부분만 구현해줬다. BFS의 경우 처음에 큐가 비어있기 때문에 큐에 입력받은 수를 푸쉬해준다. 그리고 큐에서 데이터를 하나 꺼내오고 꺼내온 데이터가 k와 같다면 while문을 빠져나가준다. while문의 조건을 true로 놔둬도 상관없다. 문제풀이이기 때문에, data가 k와 같지않은 경우는 없기때문이다. 아래의 세 가지 경우를 모두 돌면서 1) x - 1 2) x + .. 2021. 9. 27. [Swift][DFS/BFS] 백준 1260번 (DFS와 BFS) 요구능력: DFS와 BFS 그리고 스택과 큐의 이해 코드설명 : 1. 간선을 받기위함. 이렇게 받으면 a[0]이 시작노드 a[1]이 도착노드인데 서로 넣어준 이유는 간선이 양방향이기때문이다. 예를 들면 간선이 1 5 로 입력되었으면 a[0]가 1이고 a[1]이 5이다. 여기서 a[0]에만 5를 넣어주면 간선은 1->5는 갈수있는데 5->1은 못가는게 된다. 정렬해준 이유는 문제에 순서가 적혀있었기 때문이다. 마찬가지로 둘다 정렬해준 이유는 간선입력이 a[0] = 1, a[1] = 5가 있는데 간선으로 입력받는것중 5로시작하는게 없을경우 정렬이 안되기 때문이다. 2. 시작노드는 시작이기 때문에 당연히 방문처리를 한다. 그리고 방문한 노드를 바로 프린트 해주는 방식으로 했다. DFS는 깊이우선 탐색이기 때문.. 2021. 9. 9. 이전 1 ··· 4 5 6 7 다음
