목록파이썬 4963 (1)

하나씩 알아가기

[BOJ_4963] 섬의 개수

이 문제는 DFS/BFS를 이용한 시뮬레이션 문제입니다. 좌표의 범위 내에서 육지의 지역을 순회하고 이동을 할 수 없으면 카운트를 올려주는 식으로 계산합니다. 말로 하면 간단한데 좌표에서 이동할 수 있는 경우(next position)를 모두 고려해야하므로 좌표의 정보를 구해줘야 합니다. 좌표 시뮬레이션 문제는 늘 그렇듯이 dx와 dy를 더해서 다음 좌표로 이동하기 때문에 dx = [-1,-1,-1,0,0,1,1,1] dy = [-1,0,1,-1,1,-1,0,1] 를 준비합니다. 그리고 이 문제의 경우 다음 지도에서 섬의 개수가 5가 아닌 3인 것을 볼 때 상하좌우 뿐만 아니라 대각선까지 고려해 주어야한다는 것은 알 수 있습니다. 처음에는 DFS를 이용해서 여덟번의 재귀를 하는 식으로 구현했는데... I..
알고리즘 2021. 2. 3. 17:00
이전 Prev 1 Next 다음