Algorithm/Search Algorithm (2) 썸네일형 리스트형 [백준] 1043번 거짓말 1. Approach (1) 재귀 + Union Find 알고리즘 으로 접근한다. 2. DP[N][M] : n 명의 사람이 m개의 파티를 참가할 때 지민이가 최대한 과장되게 이야기를 할 수 있는 파티 개수의 최댓값. ( 이 문제에서 시간이 충분해서 DP는 큰 의미가 없다 ) -> DP[N][4] : N행, 1 - 3 열까지의 정점까지는 오는데에 필요한 최소 비용 (3) 풀이 방법 해결 방법 : #UnionFind 알고리즘을 사용한다. ( #서로소집합 ) (1) 진실을 알고있는 사람들과 같은 파티에 참가한 사람들을 모두 그래프로 잇는다. (2) 그래프가 이어진 사람들에게는 지민이가 과장된 이야기 ( 거짓말 )를 할 수가 없다. (3) 그래프가 이어진 사람들을 알고있는 사람들이라고 전부 생각하고 조건을 .. [백준] 4963번 섬의 개수 문제 위치 : https://www.acmicpc.net/problem/4963 1. Approach (1) BFS 탐색으로 접근한다. -> 플러드필 알고리즘을 응용한다면 풀 수 있다. 그래프 이론, 영상 처리에서 많이 사용하는 알고리즘이기 때문에 짚고 넘어가는 것을 권장한다. - 아이디어는 시작 좌표부터 끝 좌표까지 조건에 충족하는 좌표에서 부터 BFS를 실행한다. - 방문한 곳들은 전부 check한다. - BFS를 한 번 실행시킬 때 마다 섬의 개수를 1 증가시킨다. 2. Source Code #include #include #include #define MAX 51 using namespace std; int map[MAX][MAX]; bool check[MAX][MAX]; int dx[] = { .. 이전 1 다음