[백준] 4963번: 섬의 개수

 

https://www.acmicpc.net/problem/4963

난이도: 실버2

 

▶ 문제 탐색하기

 

알고리즘 선택

- BFS 알고리즘 사용

- DFS 알고리즘도 사용 가능하다

▶ 코드 설계하기

 

▶ 회차별 수정사항

• 문제 조건에 대각선도 걸어갈 수 있는 조건이 있었다. 그렇면 dx, dy 좌표 정해주기

▶ 정답 코드

import sys
sys.setrecursionlimit(10 ** 4) #재귀쓸 때 널기
d=[(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)] #하부터 시계반대방향으로 순회, 하 대각선 우 대각선 상 대각선 좌 대각선
def dfs(x, y):
    arr[x][y]=0
    for i in range(8):
        nx = x + d[i][0]
        ny = y + d[i][1]
        if (0<= nx < h and 0<= ny < w) and arr[nx][ny]: #범위안에 들고, arr[nx][ny]==1이면 다음위치 탐색
                dfs(nx, ny)
  
while True:
  w,h=map(int, sys.stdin.readline().rstrip().split())
  if w==0 and h==0: 
    break
  cnt=0
  arr=[ list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(h)] #visited 사용안할거면(값변경) list(list())로 하기, visited+list(tuple())
  for i in range(h):
    for j in range(w):
      if arr[i][j] :  
            dfs(i,j)
            cnt+=1
  print(cnt)

 

▶ 추가 풀이