[백준/bfs,dfs] 4963번: 섬의 개수(발전한 부분)

-문제: https://www.acmicpc.net/problem/4963

bfs로 풀려고 했다가

저번에 풀었던 아이스크림 갯수 구하는 거랑 문제가 비슷하길래 dfs로 풀어보려고 했는데 틀렸던 문제다 

 

-DFS 풀이

sys.setrecursionlimit없이 돌렸더니 RecursionError가 발생했다. dfs에서는 recursionlimit 달아주자!

 

 

스스로 짠 dfs 코드와 다른 점은 내 풀이는 dfs 실행하면 처음 받은 x,y를 기준으로 경곗값을 판단했는데, 정답풀이에서는 x,y를 이동한 nx,ny를 기준으로 경곗값 확인 후 dfs를 진행했다 

22번 라인에서 전체 행렬 탐색 중에 1인 값 만나면 거기서부터 섬의 영역 확인하는 방식으로 가야한다 

import sys
sys.setrecursionlimit(10000)

directions=[[1,1],[1,-1],[1,0],[-1,0],[-1,1],[0,-1],[-1,-1],[0,1]]
def dfs(x,y):
    s[x][y]=0
    for i in range(8):
        nx,ny=x+directions[i][0],y+directions[i][1]
        if 0<=nx<h and 0<=ny<w and s[nx][ny]==1:
            dfs(nx,ny)
                                            
while True:
    w,h= map(int,input().split())
    s=[]
    if w==0 and h==0:
        break
    for _ in range(h):
        s.append(list(map(int,input().split())))
    ans=0
    for i in range(h):
        for j in range(w):
            if s[i][j]==1:
                dfs(i,j)
                ans+=1
    print(ans)

-내가 작성한 DFS 풀이

setrecursionlimit 없고 3번 라인, 21번 라인이 정답 풀이와 다르다

 

-BFS 풀이 

from collections import deque

def bfs(x,y):
    directions=[[1,1],[1,-1],[1,0],[-1,0],[-1,1],[0,-1],[-1,-1],[0,1]]
    s[x][y]=0
    queue=deque()
    queue.append([x,y])
    while queue:
        x,y=queue[0][0],queue[0][1]
        queue.popleft()
        for i in range(8):
            nx,ny= x+directions[i][0],y+directions[i][1]
            if 0<=nx<h and 0<=ny<w :
                if s[nx][ny]==1:
                    s[nx][ny]=0
                    queue.append([nx,ny])
                    
while True:
    w,h= map(int,input().split())
    s=[]
    ans=0
    if w==0 and h==0:
        break
    for _ in range(h):
        s.append(list(map(int,input().split())))
    for i in range(h):
        for j in range(w):
            if s[i][j]==1:
                bfs(i,j)
                ans+=1
    print(ans)

 

-내가 작성한 BFS 풀이 

비슷하긴 한데 아직 부족한 부분이 좀 있다. 더 공부하자!

그래도 종료 조건에 while True: if문 사용한 거랑, 

대각선으로 이동하는 거 direction 리스트 구현한 거, 

bfs()함수 맞게 구현한 것만 해도 많이 발전했다!!