[Solved] BOJ: 4963 | 섬의 개수

문제

근접해있는 섬들을 이어 하나의 섬으로 침.
전체 맵에서 섬 개수 카운트

입력

• 첫째줄: 지도의 너비 w, 높이 h, (w, h <= 50)
• 둘째줄~2+h번째줄: 지도, 1 == 땅, 0 == 바다

출력

섬의 개수

---

접근

근접해있는거 이어서 하나로 치고 전체 몇개인지 카운트하는 것은
bfs 그래프 탐색으로 풀면된다.
다만 4방향이 아닌 대각선까지 총 8방향에 대해서 구하면 됨

풀이

입력

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

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

• 입력 받아오기
• 0 0 이 입력으로 들어오기 전까지 계속 테스트 케이스를 돌릴 수 있음

방향키

d = [(1, 0), (0, -1), (-1, 0), (0, 1), (1, 1), (1, -1), (-1, -1), (-1, 1)] # 하 좌 상 우, 우하, 좌하, 좌상, 우상

• 8 방향에 대한 방향키 저장해두기

bfs

cnt = 0
    for i in range(H):
        for j in range(W):
            if m[i][j] == 1:
                # bfs
                cnt += 1
                m[i][j] = 0
                queue = deque([(i, j)])
                while queue:
                    y, x = queue.popleft()
                    for dy, dx in d:
                        if 0 <= y+dy < H and 0 <= x+dx < W:
                            if m[y+dy][x+dx] == 1:
                                m[y+dy][x+dx] = 0
                                queue.append((y+dy, x+dx))

• 전체 맵을 순회하다가
• 땅(1)을 발견하면 근접한 땅들을 순회함 (bfs)
• 발견한 땅을 queue의 root로 넣어주어 bfs 시작
• 8방향에 대해 이동했을 때,
  • 맵을 벗어나지 않는지,
  • 이동한 곳이 땅(1)인지 체크
• 조건에 다 만족한다면 이동한 곳을 바다(0)으로 바꿔줌 -> visited 처리하기: visted 리스트 따로 선언하지 않고 그냥 이렇게 해도 됨
• 큐에 이동한 땅 추가

---

전체 코드

from collections import deque
import sys
input = sys.stdin.readline

d = [(1, 0), (0, -1), (-1, 0), (0, 1), (1, 1), (1, -1), (-1, -1), (-1, 1)] # 하 좌 상 우, 우하, 좌하, 좌상, 우상

def solutions(W, H):
    m = []
    for _ in range(H):
        m.append(list(map(int, input().split())))

    cnt = 0
    for i in range(H):
        for j in range(W):
            if m[i][j] == 1:
                # bfs
                cnt += 1
                m[i][j] = 0
                queue = deque([(i, j)])
                while queue:
                    y, x = queue.popleft()
                    for dy, dx in d:
                        if 0 <= y+dy < H and 0 <= x+dx < W:
                            if m[y+dy][x+dx] == 1:
                                m[y+dy][x+dx] = 0
                                queue.append((y+dy, x+dx))
    return cnt

if __name__ == "__main__":
    while True:
        w, h = map(int, input().split())
        if w == 0 and h == 0:
            break
        print(solutions(w, h))

• 아주 단순한 bfs 문제다

---

제출

• 근데 자꾸 시간초과 났었음;;;

시간초과 났던 코드

# 시간초과
from collections import deque
import sys
input = sys.stdin.readline

d = [(1, 0), (0, -1), (-1, 0), (0, 1), (1, 1), (1, -1), (-1, -1), (-1, 1)] # 하 좌 상 우, 우하, 좌하, 좌상, 우상

def solutions(W, H):
    m = []
    for _ in range(H):
        m.append(list(map(int, input().split())))

    cnt = 0
    for i in range(H):
        for j in range(W):
            if m[i][j] == 1:
                # bfs
                cnt += 1
                queue = deque([(i, j)])
                while queue:
                    y, x = queue.popleft()
                    m[y][x] = 0
                    for dy, dx in d:
                        if 0 <= y+dy < H and 0 <= x+dx < W:
                            if m[y+dy][x+dx] == 1:
                                queue.append((y+dy, x+dx))
    return cnt


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

• 위랑 아주 차이가 없어보이지만
• visited를 체크해주는 위치가 다르다

# 시간초과
while queue:
    y, x = queue.popleft()
    m[y][x] = 0
    for dy, dx in d:
        if 0 <= y+dy < H and 0 <= x+dx < W:
            if m[y+dy][x+dx] == 1:
                queue.append((y+dy, x+dx))

• m[y][x] = 0 visited 체크를 큐에서 값을 꺼내고 한다.
• 8방향에 대해 순회를 할 때는 일단 값이 1이면 다 넣는거다
• 그리고 꺼낼 때 0으로 바꿔주는 것이다
• 이러면 분명 중복으로 큐에 들어가게 되는 위치들이 많이 발생한다

while queue:
    y, x = queue.popleft()
    for dy, dx in d:
        if 0 <= y+dy < H and 0 <= x+dx < W:
            if m[y+dy][x+dx] == 1:
                m[y+dy][x+dx] = 0
                queue.append((y+dy, x+dx))

• m[y+dy][x+dx] = 0 visited 체크를 큐에 값을 넣기 전에 한다.
• 큐에 넣기 전에 0으로 바꿔주기 때문에
• 근접한 위치에서 bfs가 일어나고 있을 때 0으로 이미 바뀐부분은 큐에 들어가지 않는다.