[python 파이썬] 백준 4963번 섬의 개수

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

4963번: 섬의 개수

 

처음 딱 접했을 때 문제는 "이것이 취업을 위한 코딩테스트다"에 실린 음료수얼려먹기 문제와 유사했다. 

하지만 조금 다른 점이 있다. 

 

핵심

1. 덩어리 개수를 구할 것 

2. 상하좌우로 움직일 수 있을 뿐만 아니라 대각선 방향으로도 움직일 수 있다.

 

 

음료수얼려먹기 문제가 dfs로 풀려서 나도 dfs로 처음에 구현했다. 

근데 여론을 보니 dfs와 bfs 모두 가능하다고 한다. 

따라서 두가지 방법으로 모두 풀었다. 

 

여기서 놓친 것은 x,y / w,h 를 헷갈려서 반대로 하니 안풀렸다 ㅠㅠ 

유의하자!!

 

 

DFS

 

def dfs(y,x):
    # 범위 벗어나는 경우 건너뛰기
    if x < 0 or x >= w or y < 0 or y >= h:
        return False
    # 바다인경우 건너뛰기
    # if graph[x][y]==0:
    #     return False

    # 섬인경우 재귀
    if graph[y][x] == 1:
        #방문처리
        graph[y][x] = 0
        # 상하좌우 탐색
        dfs(y,x-1)
        dfs(y,x+1)
        dfs(y-1,x)
        dfs(y+1,x)
        # 대각선 탐색
        dfs(y-1,x-1)
        dfs(y-1,x+1)
        dfs(y+1,x-1)
        dfs(y+1,x+1)
        return True
    return False


while True:
    w,h = map(int,input().split())

    if w == 0 & h ==0 :
        break

    graph = []
    for _ in range(h):
        graph.append(list(map(int,input().split())))

    result = 0
    for i in range(h):
        for j in range(w):
            if dfs(i,j) == True:
                result += 1
    print(result)

 

 

BFS

 

# 2) bfs로 풀어보기, w와 h 헷갈
# 상하좌우, 대각선
from collections import deque

dx = [-1,1,0,0,-1,+1,-1,+1]
dy = [0,0,-1,1,-1,-1,+1,+1]

def bfs(y,x):

    queue= deque()
    queue.append((y,x))
    while queue:
        y,x = queue.popleft()
        for i in range(8):
            nx = x+dx[i]
            ny = y+dy[i]

            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue
            if graph[ny][nx]==0:
                continue

            if graph[ny][nx]==1:
                graph[ny][nx]=0
                queue.append((ny,nx))



while True:
    w,h = map(int,input().split())
    if w == 0 and h == 0 :
        break

    graph = []
    for _ in range(h):
        graph.append(list(map(int,input().split())))

    result = 0
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                result += 1
                bfs(i,j)

    print(result)