코딩테스트 - 패스트캠퍼스 챌린지 32일차

수강한 강의

Part 3. 알고리즘 유형별 풀이

Chapter 02 알고리즘
- 그래프 탐색 (Graph Search, DFS & BFS) - 응용 편 1

학습 후기
격자형 그래프
해당 좌표를 중심으로 상, 하, 좌, 우를 확인해가며 이동할 수 있는 격자인지 확인
이때 중심 좌표를 기준으로 상, 하, 좌, 우 좌표는 {{1, 0}, {0, 1}, {-1, 0}, {0, 1}}을 사용하여 확인한다.
https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

정점: O(N^2)
간선: O(N^2 * 4)
탐색 시 BFS, DFS 모두 시간 복잡도 O(N^2)

https://www.acmicpc.net/problem/2251

2251번: 물통

정점: O(8*10^6): A, B, C 각 물통의 최대 리터 200, 200 ^ 3 가지의 상태를 나타낼 수 있음.
간선: O(8*10^6 * 6): A > B, A > C, B > A, B > C, C > A, C > B 물통의 물을 이동할 수 있는 경우의 수 6가지
탐색의 시간 복잡도는 DFS, BFS 모두 O(8*10^6)이다.

해당 문제를 풀기 위해서 물통의 상태를 나타내는 정점을 표현하기 위해 구조체(클래스)를 만들어 푼다.

https://www.acmicpc.net/problem/14502

14502번: 연구소

문제 입력 범위 (3 ≤ N(세로), M(가로) ≤ 8)
정답의 최대치: 모두 안전 영역일 경우 O(N^2)
문제 접근
1. 바이러스 노출 지역 확인: 격자형 그래프로 보고 탐색한다.
2. 완전 탐색으로 3칸의 벽을 세울 수 있는 경우의 수를 다 구해본다.
빈 공간(N*M)에 최대 3개의 칸으로 세울 수 있는 경우의 수: 8*8 C 3 = 64 * 63 * 62 / ( 3 * 2 * 1) = 41664
3. 벽을 세울 수 있는 경우의 수마다 탐색을 한다. O(41664) * O(탐색)
4. 바이러스가 있는 모든 지역에서 BFS 시작(Multisource BFS), 이때 탐색 시간 복잡도 O(N ^ 2)
총 O(41664) * O(N ^ 2) = O(41664) * O(64) = 2,666,496로 충분히 계산 가능하다.

DFS, BFS는 알고리즘 단골 문제라 유형도 많아서 기본 편, 응용 편 1, 2까지 있다 다음 편 까지 배우고 여러 문제를 접하며 확실히 익혀야겠다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.