[백준/Python] 4963 : 섬의 개수

4963번: 섬의 개수 (acmicpc.net)

4963번: 섬의 개수

 

 

소스코드

 

설명

• sys.setrecursionlimit()를 이용해 재귀호출의 최대 깊이 증가
• 하나의 섬을 둘러싸고 있는 최대 8개의 섬이 존재하며 각 섬으로 이동 가능하므로 현재 섬의 좌표가 (0,0)일 때, 각 섬의 x좌표와 y좌표를 dx, dy 리스트로 생성
• w, h을 입력받고 둘다 0이라면 while문 종료
• 현재 섬과 바다의 위치를 보여주는 2차 배열 a 생성
• a와 똑같은 위치의 칸에 방문 여부를 알려주는 2차 배열 visit 생성
  • 현재 아무 섬도 방문하지 않았으므로 모두 False로 생성
• a의 한 칸마다 이동가능한 섬을 확인하기 위해 h열 w행의 칸을 모두 조사
  • 현재 위치인 a[i][j]가 1로 섬이고 visit가 False로 아직 방문하지 않았다면 dfs함수 호출 후 cnt 1증가
  • 현재 위치의 상하좌우 + 대각선의 모든 섬들을 for문을 이용해 모두 확인
    1. 현재 위치의 주변 위치가 w x h를 벗어나지 않고
    2. 섬이며
    3. 방문하지 않았다면
  • dfs함수를 주변 위치 정보를 이용해 재귀 호출
  • 위 조건들을 불만족시 재귀 호출하지않고 다음 루프로 점프
• 총 cnt의 수를 출력