Algorithm236 [Swift][BFS] 백준 16946번 (벽 부수고 이동하기4) 요구능력 : BFS 코드설명 : https://go-coding.tistory.com/54 [백준 16946번] 벽 부수고 이동하기4(java) 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 go-coding.tistory.com 위의 분 께서 설명을 너무 잘해주셔서 덕분에 문제를 쉽게 이해할 수 있었다. 이 문제는 벽이 있는 위치에서 현재 위치한곳의 벽을 부수고 그 벽을 부순 자리에서 몇번 이동이 가능한지를 묻는 문제이다. 가장 쉬운 방법은 1이 있는 위치에서 BFS를 돌리는건데, 그냥 그렇게만 하면 O(n * m)의 시간복잡도를 가지므로 최악의 경우.. 2022. 3. 7. [Swift][DP] 백준 11058번 (크리보드) 요구능력 : DP 코드설명 : 의식의 흐름대로 문제를 풀게됬다. 일단 2번부터 4번조건은 처음에는 세개가 다같이 발동해야한다. 1번부터 6번까지는 그냥 A를 찍는게 수가 훨씬 많다고 생각해서 dp[i]에 i를 넣어주었다. 그리고 i가 7일때 부터는 전체선택, 복사, 붙여넣기 등의 과정이 들어가는게 A를 더 많이 찍게된다. n이 7일 때를 가정해서, 점화식을 구해보면 버튼을 총 7번 누를 수 있는데 이 중에서 전체선택, 복사, 붙여넣기를 하려면 버튼 누르는 수가 3번이 있어야한다. 그럼 우리는 A를 최대한 찍고 저 3번을 눌러야한다. 그렇기 때문에 바로 dp[i - 3]인 곳에서 전체선택,복사,붙여넣기를 하면 버튼은 총 7번 누르게된다. 그리고 붙여넣기를 했기 때문에 dp[i - 3]의 A의 개수에서 2배.. 2022. 3. 2. [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][백트래킹][LV_3] 양과 늑대 요구능력 : 2진트리, 백트래킹 코드설명 : 처음에 배열로 edges를 연결리스트식으로 만들어서 방문했던곳을 다시 들리는(위로다시올라오는) 대참사가 발생했다. dictionary로 아래와 같이 넣으면 한방향(본인 위치의 아래방향)으로 방문하기 편하므로 dictionary를 사용했다. 백트래킹이라고 생각한이유는 모든경우를 다 세어봐야 하기 때문이다. dfs(현재노드, 다음에 방문할 수 있는 노드, 양의 카운트, 늑대의 카운트)로 구성했다. 이렇게 구성한 이유는 양과 늑대의 카운트같은 경우 dfs()함수가 리턴되면 따로 -처리를 해주지 않아도 되기 때문이고(전역으로 선언 시 따로 -처리를 해줘야함), 현재노드 같은 경우에는 시작노드로 0을 전달해줘야 하는것도있고 굳이 0을 전달 안해주고 0으로 시작하더라도 .. 2022. 2. 26. 이전 1 ··· 14 15 16 17 18 19 20 ··· 59 다음
