목록백준1012 (1)

시작이 반

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

배추흰 지렁이가 인접한(상, 하, 좌, 우) 배추를 보호 한다고 한다. 즉, 이 문제는 배추의 영역을 구하는 문제이다. DFS, BFS둘다 사용 할 수 있지만 DFS의 경우 재귀의 횟수에 따라 메모리, 시간초과가 뜰 수 있다. 이때 sys.setrecursionlimit(n) 을 사용하여 제귀횟수를 제한할 수 있지만 BFS를 사용하는 것이 좋아보인다. 여기서 노드는 배열의 좌표라고 생각한다. DFS 시작 노드에서 인접한 노드 선택하여 방문처리를 하고 탐색을 들어간다. 더이상 탐색할 노드가 없으면 이전노드에 연결되어 있는 점들 중 방문하지 않고 다음으로 큰 노드을 탐색한다. BFS BFS는 큐를 이용하여 문제를 풀 수 있다. 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내..
알고리즘/백준 2021. 1. 6. 14:28
이전 Prev 1 Next 다음