[백준] BOJ 16000 섬
·
PS/BOJ
https://www.acmicpc.net/problem/16000  | Solved.ac 난이도 : P2 | 문제 추천도 : 6/10  🏷️ 그래프 이론, 탐색 단절점을 이용한 풀이도 있다고 한다. 하지만 단순 그래프 탐색 풀이보다 어렵다고 봄.  풀이 1. $($상하좌우 네방향으로$)$ 이어져있는 육지들을 각각의 그룹으로 묶어준다. 2. 최외곽에는 항상 바다가 주어지므로 $($0,0$)$에서부터 바다를 탐색한다.육지를 지나갈 수 없는 벽으로 보고 갈 수 있는 바다를 탐색한다.상하좌우+4개의 대각선 방향으로 탐색한다.⭐ KeyPoint -  대각선 방향은 어떤 육지를 거쳐 바깥쪽 바다로 가는 경우이다.아래는 대각선 방향으로 안쪽 바다 -> 육지 -> 바깥쪽 바다로 가는 경우를 설명한다.바다 바다 바..
ddirori가 PS하는 블로그
'graphs' 태그의 글 목록