⌨️ 파이썬 코딩테스트 유형별 풀이법
date
‣
slug
python-ps
status
Published
tags
PS
Algorithm
summary
파이썬 코딩테스트 유형별 풀이법
type
Post
1. BFS
너비우선탐색은 큐를 이용해서 풀어낸다.
- dx, dy를 이용해 상하좌우 네 방향을 모두 탐색할 수 있도록 하고,
- vis 배열을 이용해 이미 탐색된 배열은 탐색하지 않는다. (탐색하면 0으로 변경)
- 또는 vis 배열을 활용해 거리를 측정할 수도 있다. (vis[cur] +1으로 변경)
- 탐색하려는 인덱스가 범위를 벗어났는지 반드시 체크한다.
BFS 기본문제인 백준 1926번: 그림 문제이다.
도화지에서 모든 그림의 개수와 가장 큰 그림의 넓이를 출력하는 문제이다.
###으로 감싼 부분이 일반적인 BFS 구현의 형태이고, 그 외에는 모든 그림을 탐색하기 위해 while문을 활용하였다.
필요한 경우 board와 vis 배열을 각각 두고 활용하여도 되고, 여기서 큐 대신 스택을 사용하면 DFS가 된다.
2. DFS
깊이 우선 탐색은 스택을 이용해서 풀어낸다. 나머지 조건은 BFS와 같다.
3. 재귀 및 백트래킹
- 재귀는 N번째 항과 N+1번째 항의 관계를 찾으려 노력하자.
- 백트래킹은 일종의 가지치기 완전탐색이다. 시간복잡도가 O(2^N)이니 N이 20을 넘어가면 시도하지 말고, 카운트는 되도록이면 마지막 노드(return 직전)에서 하는 것이 좋다.
- 둘 다 탈출조건을 주의하자.