알고리즘) 백준 2206번 벽 부수고 이동하기 Swift
https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
예제
| 입력 | 출력 |
| 6 4 0100 1110 1000 0000 0111 0000 |
15 |
| 4 4 0111 1111 1111 1110 |
-1 |
| 5 10 0000011000 1101011010 0000000010 1111111110 1111000000 |
14 |
문제 접근
우선 단순하게 생각을 해 보았습니다.
1. 벽을 한 개 부숴도 된다면 한 개 씩 부숴서 거리가 제일 짧게 나오는 결과를 출력한다.
하지만 이 방법은 정말 많은 시간이 소요돼서 실패할 수 밖에 없습니다. (그럼에도 불구하고 시도는 해보았습니다..)
다음엔 다른 사람들의 풀이를 참고하였습니다.
2. 가다가 벽을 처음 만나면 부수고 이동 횟수를 카운트한다.
풀이를 보면서 이해가 안갔던 부분은 "벽을 만나도 안부수고 있다가 나중에 부수는 경우는 어떻게 체크하는거지?" 였는데
결론적으로는 그리디 개념이 합쳐진 BFS라고 생각해야 합니다. 만나면 부숩니다.
부쉈는지 안부쉈는지 여부는 위치를 나타내는 2차원 배열을 확장하여 3차원 배열에 넣어 동기화해줍니다.
- visited[0][0][0] = visited[0][0] 위치인데 벽을 아직 안부쉈다.
- visited[1][2][1] = visited[1][2] 위치인데 벽을 만나서 이미 부쉈다.
보통 알고리즘 풀이법을 검색하면 C, C++, 파이썬이 나오기 때문에 로직만 참고하고 디테일한 부분은 직접 손봐야 합니다.
그 과정도 쉽지 않았는데 예를 들자면,
Swift 언어로 구현 시 주의할 점이 Array의 removeFirst() 메서드를 사용했을 때 O(n) 시간복잡도가 발생합니다.
시간 초과 문제를 해결하기 위해 Queue에서 현재 위치를 가리키는 index를 두었습니다. (하지만 메모리를 많이 잡아먹습니다.)
작업을 함수로 선언하고 return 값을 print 하는 것 보다 전역에서 수행하는 것이 메모리를 적게 쓸 수 있습니다.