<dfs bfs> 백준 4963번. 섬의 개수 (오답노트) / 시간초과(BFS,DFS)->해결

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

4963번: 섬의 개수

 

너어무 어려웠당..

혼자 해결하지 못해 다른 분들의 코드를 참고해 이해하였다. 이해하고 나서 새로 짜봤다! 

이걸 생각해낸 여러분 천재신가요?

#<완성코드 x>
def dfs(x,y):
  global cnt
  graph[x][y] = 0
  for i in range(8):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0<=nx<h and 0<=ny<w:
      if graph[nx][ny]: #방문할 수 있으면 즉, 땅이면
        dfs(nx,ny)
        
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
w, h = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(h)]
cnt = 0

for i in range(h):
  for j in range(w):
    if graph[i][j]: #1이면
      cnt += 1
      dfs(i,j)
    
print(*graph, sep = "\n")
print(cnt)

결과는 다음과 같다.

우선, while문에 넣기 전에 하나의 케이스만 성공해보자 라는 생각으로 작성하였다. 즉, 아직 완성된 코드가 아니다!

dfs 코드를 작성하는건 크게 어렵지 않았는데, 1이 연결된 경우에만 어떻게 cnt를 늘리는지 해결하지 못했었다. 

반복문을 통해 첫 요소부터 마지막 요소까지 dfs를 실행해주어야 한다. 

 

dfs가 실행되면, 그 위치를 0으로 바꿔주는 걸 생각하지 못했다.. 이럼 visited 리스트를 굳이 적을 필요없겠군..대박🙄

왜 0으로 바꿔주는지는 다들 알 것이다! 다시 방문하지 않기 위해 0_<-🤍

결과는 위와 같은데, graph 모든 요소를 돌면서 0으로 바꿔줬기 때문에 저렇게 출력되고, cnt도 제대로 출력된다.

 

이제 bfs로도 구현해보자!

#<완성 코드 x>

def bfs(x,y):
  q = deque()
  q.append( (x,y) )
  while q:
    x,y = q.popleft()
    graph[x][y]=0
    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]
      if (0<=nx<h and 0<=ny<w):
        if graph[nx][ny]: #땅이면
          q.append((nx,ny))
          graph[nx][ny] = 0

같은 결과가 나왔다. 아 재밌다ㅏ... 분명히 문제 안 풀릴 땐 너어무 재미없었는데 ㅋㅎㅋㅎㅋㅎㅋ

 

이제 while문을 통해 전체 코드를 완성해주자.

#<완성코드>
from collections import deque
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
def dfs(x,y):
  global cnt
  graph[x][y] = 0
  for i in range(8):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0<=nx<h and 0<=ny<w:
      if graph[nx][ny]: #방문할 수 있으면 즉, 땅이면
        dfs(nx,ny)
        
def bfs(x,y):
  q = deque()
  q.append( (x,y) )
  while q:
    x,y = q.popleft()
    graph[x][y]=0
    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]
      if (0<=nx<h and 0<=ny<w):
        if graph[nx][ny]: #땅이면
          q.append((nx,ny))
          graph[nx][ny] = 0  

#선언
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

while True:
  w, h = map(int, input().split())
  graph = [list(map(int, input().split())) for i in range(h)]
  cnt = 0
  if w == 0 and h == 0: break #종료조건
    
  for i in range(h):
    for j in range(w):
      if graph[i][j]: #1이면
        cnt += 1
        bfs(i,j)
        #dfs(i,j)
      
  print(cnt)

답은 똑같이 나오지만, dfs일 때, 시간초과가 떠서

import sys
sys.setrecursionlimit(10000)

을 추가해주니 정답처리가 되었다..

파이썬은 역시나 너무 무겁다................c++은 가벼운데 흑흑