목록백준1926 (1)

시작이 반

[백준] 1926번(python 파이썬)

처음에 DFS로 풀었지만 메모리 초과가 나왔다. 재귀에 이상이 있음을 확인하였다. 입력크기가 n(1 ≤ n ≤ 500), m(1 ≤ m ≤ 500) 이기 떄문에 재귀로 풀면 메모리 초과가 뜬다. 때문에 BFS를 사용하여 풀었다. BFS (2차원배열 인접 리스트 확인 (상, 하, 좌, 우)) dx, dy를 이용하여 상, 하, 좌, 우 확인 for 문을 이용하여 2차원 배열의 모든 좌표 확인 1. 방문하지 않고, 배열의 값이 1일 경우 큐에 삽입하고 방문 처리를한다. 2. 큐에서 해당 좌표를 꺼내 그 좌표의 상, 하, 좌, 우를 확인한다. 상, 하, 좌, 우에 1이 있고 방문하지 않았다면 큐에 삽입후 방문처리를한다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. (큐가 빌때까지) from c..
알고리즘/백준 2021. 1. 5. 19:30
이전 Prev 1 Next 다음