알고리즘/그래프(Graph)
-
[백준 4963] - [그래프] - 섬의 개수 (JAVA)알고리즘/그래프(Graph) 2018. 12. 28. 14:43
문제 링크 : https://www.acmicpc.net/problem/4963 이 문제는 그래프 기본 문제이다. DFS 혹은 BFS로 풀면 되고 정답률이 48%로 어렵지 않은 문제이고 그렇기에 간단하게 접근 할 수 있다. 좌표 기준 가로, 세로, 대각선으로 움직일수 있는 땅을 하나의 섬이라 간주한다고 한다. 한번 탐색할때 가로 세로 뿐만 아니라 대각선으로도 탐색을 진행하면 임의의 좌표 [Y,X] 와 하나의 섬인 경우를 확인할 수 있다. 속도를 줄이기 위해 땅의 좌표들은 입력을 받을때 큐에 저장하였고 큐에서 하나씩 추출해가면서 탐색을 진행했다. 소스1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484..