[Python] 4963번 섬의 개수 / 재귀함수.ver

밀린 알고리즘 공부를 시작했다.

DFS와 BFS부터 시작하는 게 좋을 것 같다고 해서 4963번을 풀게 되었다.

이번 알고리즘은 DFS로 풀었다.

 

def island(yi,xi):
    dy=[1,0,-1,1,-1,1,0,-1]
    dx=[-1,-1,-1,0,0,1,1,1]
    
    visited[yi][xi]=True
    
    for i in range(8):
        y=yi+dy[i]
        x=xi+dx[i]
        if 0<=x<w and 0<=y<h:
            if m[y][x]==1 and visited[y][x]==False: #m[y][x]==1 확인하지 않았음
                island(y,x)
                
while True:
    w,h=map(int,input().split())
    
    if w==0 and h==0:
        break
        
    else:
        cnt=0
        m=[] #map
        visited=[[False for i in range(w)] for i in range(h)] #한 번 방문 후 섬 없다고 하면 됌
        for _ in range(h):
            m.append(list(map(int,input().split())))
            
        for y in range(h):
            for x in range(w):
                if m[y][x]==1 and visited[y][x]==False:
                    island(y,x)
                    cnt+=1
        print(cnt)

처음에 코드를 돌렸을 때 첫 번째 테스트케이스 말고 뒤에 케이스에 모두 1이 나오길래 뭐가 문제인지 몰랐다.

나중에 지피티로 확인해보니 재귀함수로 다시 들어갈 때 방문하지 않은 경우만 고려하고, 섬인 경우(1)의 조건을 빼었던 것이 문제였다.

다시 수정하니까 제대로 돌아갔다. 

 

그리고 이렇게 푼 알고리즘을 스터디원과 함께 풀이를 하였는데 visited를 굳이 안 써도 되겠다는 조언을 해주셨다.

visited를 쓰지 않고 방문한 후 섬이 없다고 하면 굳이 변수를 하나 더 설정할 필요 없다고 해주셔서 고쳐보았다.

def island(yi,xi):
    dy=[1,0,-1,1,-1,1,0,-1]
    dx=[-1,-1,-1,0,0,1,1,1]
    
    m[yi][xi]=0 #섬을 방문한 경우 0으로 바꿔줌
    
    for i in range(8):
        y=yi+dy[i]
        x=xi+dx[i]
        if 0<=x<w and 0<=y<h:
            if m[y][x]==1: 
                island(y,x)
                
while True:
    w,h=map(int,input().split())
    
    if w==0 and h==0:
        break
        
    else:
        cnt=0
        m=[] #map
        for _ in range(h):
            m.append(list(map(int,input().split())))
            
        for y in range(h):
            for x in range(w):
                if m[y][x]==1:
                    island(y,x)
                    cnt+=1
        print(cnt)

이렇게 수정하였더니 훨씬 간단해졌다.

 

작성한 코드를 백준에 내니 문제가 또 생겼었다.

이 문제 대해서는 

https://www.acmicpc.net/board/view/93923

질문 게시판의 글에 도움을 받아 

import sys
sys.setrecursionlimit(10**6)

코드를 추가하였더니 해결되었다.