백준177 [Swift][BFS] 백준 9376번 (탈옥) 요구능력 : 0-1 BFS알고리즘 코드설명 : 이 문제는 다익스트라로도 풀린다고 하고 0-1 BFS알고리즘 으로도 문제가 풀린다. 나는 0-1 BFS알고리즘으로 공부하고 여러군데를 참고해서 문제를 풀어봤다. 나는 처음에 죄수 2명으로 BFS를 해서 문을 최소로 구하고 탈출시켜봤는데, 예제 입력 5 9에서는 성공했지만 예제 입력 5 11에서는 성공못했다. 답은 0 이지만 내 출력은 1이 나와서인데, 내 출력이 1이 나온이유는 위에 있는 문을 부수면 가장자리(x == 0 or y == 0 or x == h or y == h)로 올경우 종료조건을 줬기 때문이다. 문을 부수더라도 가장최소한으로 움직이는 방법이 되버린것이다. 예제 입력 5 11에서 성공하려면 무조건 가장자리에 간다고해서 종료조건이라는걸 만들면 안.. 2022. 2. 28. [Swift][DP] 백준 2294 (동전 2) 요구능력 : DP 코드설명 : dp의 초기값을 10001로 설정해준 이유는 이 문제가 최솟값을 찾는 문제이기 때문에 최대값으로 설정해준것이다. 10001이 최댓값인 이유는 k의 범위가 10000까지 이기때문에 여기서 나올 수 있는 가장 큰 수는 1로 10000까지 만들어서 1이 10000개인 경우이다. 위의 사진은 직접 행과 열로 나열해서 사용해야하는 동전의 개수를 적은것이다. 1원으로 1~15까지 만들 수 있는 경우의 수는 1개 ~ 15개이다. 하지만, 5원으로 1 ~ 15까지 만드려면? 뭔가 복잡해지는것 같을 수 있다. 우선, 1원으로 1 ~ 15까지 만들어보자. 행과 열을 만들어야겠다. for i in 0.. 2022. 2. 21. [Swift][DFS] 백준 18290번 (NM과 K(1)) 요구능력 : DFS 코드설명 : DFS문제이지만, 마냥 순열로 풀어버리면 DFS에 O(n^2)이 나와버려서 통과가 안된다. 그래서 처음에는 선택으로 가려고 x와 y둘다 이전에 방문했던 부분 다음 부분부터 방문하게했더니 , 그렇게 하면 탐색하는 줄이 다음줄로 넘어가도 y좌표도 이전에 방문했던 부분의 다음부분부터 방문해버리는 문제가 생겨서 x만 중복을 최대한 줄이는 쪽으로 문제를 해결했다. 이거 외에 이 문제에서 핵심이라고 볼만한것은 바로 이 부분이다. func check(_ x: Int, _ y: Int) -> Bool{ for i in 0..= n || ny = m{ continue } if visited[nx][ny] { //현재 좌표와 인접한 곳이 이전에 방문한적 있었다면 현재좌표.. 2022. 2. 17. [Swift][BFS] 백준 12906번 (새로운 하노이 탑) 요구능력 : Set, BFS 코드설명 : 원판움직이는 경우를 BFS로 표현하는것은 어렵지 않다. A에 원판이 있는경우 하나를 빼서 B에 넣는경우를 큐에 넣어주고 C에 넣는경우를 큐에 넣어주면된다. B와 C도 마찬가지로 하면된다. 이 문제에서 가장 중요한점은 방문처리를 어떻게 하느냐이다. 나는 처음에 방문처리를 안했다가 무한루프에 빠지고 말았다. 이런문제를 나처럼 처음 접하는 사람들은 당황하게 될 것이다. 방문처리를 해야되는데,, 문자열이네? 여태 좌표만 방문처리해봐서 문자열은 할줄 모르겠다 싶었다. Set을 활용하면 되더라. 다른 언어들은 Set에 큐에 사용한 형식그대로 사용하는데, Swift는 따로 custom을 해줘야한단다. 그냥 String으로 처리해줘야겠다. 각 모든 배열을 joined()로 st.. 2022. 2. 16. 이전 1 ··· 7 8 9 10 11 12 13 ··· 45 다음
