isPowerfulBlog

[Solved] BOJ: 4963 | 섬의 개수 본문

Algorithm

[Solved] BOJ: 4963 | 섬의 개수

왕밤빵도라에몽 2023. 2. 2. 20:07

image

문제

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

입력

  • 첫째줄: 지도의 너비 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 문제다

제출

image

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

시간초과 났던 코드

# 시간초과
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으로 이미 바뀐부분은 큐에 들어가지 않는다.