[Python] 백준 4963번 - 섬의 개수

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

4963번: 섬의 개수

 

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 그래프 이론
 - 그래프 탐색
 - 너비 우선 탐색(BFS)
 - 깊이 우선 탐색(DFS)

 

 

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

 

---

 

딱 보자마자

 

이건 DFS, BFS문제라는 걸 알았다.

 

이런 문제를 많이 풀어보니 눈에 들어온다.

 

하지만 어떻게 푸는가는 다른문제이다.

 

난 이 문제를 여러 가지 방법으로 풀었다.

 

1. 처음부터 (0, 0)부터 끝까지 (w, h)까지 bfs를 하며 찾기

-> 이 방법은 

 

5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1

 

과정에서 틀려먹었다.

 

나는 12시부터 11시 방향으로 도착하는 시계방향으로 dx, dy를 잡았다.

 

그랬더니 1을 7개까지 찾고 1들 사이에 visit이 1 사이에 갇혀버려 틀린 답이 되었다.

 

틀린 코드 보기

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

def bfs(x, y, w, h):
    cnt = 0
    q = deque()
    q.append((x, y))
    
    visit = [ [0] * w for _ in range(h)]
    
    dx = [-1, -1, 0, 1, 1, 1, 0, -1]
    dy = [0, 1, 1, 1, 0, -1, -1, -1]
    while q:
        now_x, now_y = q.popleft()
        visit[now_x][now_y] = 1
        
        if data[now_x][now_y] == 1:
            for i in range(8):
                nx = now_x + dx[i]
                ny = now_y + dy[i]
                if 0 <= nx < h and 0 <= ny < w:
                    if visit[nx][ny] == 0 and data[nx][ny] == 1:
                        q.append((nx, ny))
                if i == 7 and len(q) == 0:
                    cnt += 1
                    for i in range(8):
                        nx = now_x + dx[i]
                        ny = now_y + dy[i]
                        if 0 <= nx < h and 0 <= ny < w:
                            if visit[nx][ny] == 0:
                                q.append((nx, ny))
                                break
        else:
            for i in range(8):
                nx = now_x + dx[i]
                ny = now_y + dy[i]
                if 0 <= nx < h and 0 <= ny < w:
                    if visit[nx][ny] == 0:
                        q.append((nx, ny))
                        break
    return cnt
            

while True:
    w, h = map(int, input().split())
    if w == 0:
        break
    data = []
    for _ in range(h):
        data.append(list(map(int, input().split())))
    
    cnt = bfs(0, 0, w, h)
    print(cnt)

그리고 애초에 위 코드는 메모리 초과가 발생했다.

 

---

2.  visit에 1들 사이에 갇혀버리니 처음부터 끝까지 돌자

 

def find()를 통해

visit이 아직 0인 좌표를 구하여 리턴하는 함수를 추가하였다.

 

문제는 잘 풀린 듯했지만 시간초과가 발생했다.

 

틀린 코드 보기

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

def find(w, h, visit):
    for i in range(h):
        for j in range(w):
            if visit[i][j] == 0:
                return i, j
    else:
        return -1, -1

def bfs(x, y, w, h):
    cnt = 0
    q = deque()
    q.append((x, y))
    
    visit = [ [0] * w for _ in range(h)]
    
    dx = [-1, -1, 0, 1, 1, 1, 0, -1]
    dy = [0, 1, 1, 1, 0, -1, -1, -1]
    while q:
        now_x, now_y = q.popleft()
        visit[now_x][now_y] = 1
        
        if data[now_x][now_y] == 1:
            for i in range(8):
                nx = now_x + dx[i]
                ny = now_y + dy[i]
                if 0 <= nx < h and 0 <= ny < w:
                    if visit[nx][ny] == 0 and data[nx][ny] == 1:
                        q.append((nx, ny))
                if i == 7 and len(q) == 0:
                    cnt += 1
                    nx, ny = find(w, h, visit)
                    if nx != -1:
                        q.append((nx, ny))
                    break
        else:
            nx, ny = find(w, h, visit)
            if nx != -1:
                q.append((nx, ny))
    return cnt
            

while True:
    w, h = map(int, input().split())
    if w == 0:
        break
    data = []
    for _ in range(h):
        data.append(list(map(int, input().split())))
    
    cnt = bfs(0, 0, w, h)
    print(cnt)

---

3. land를 찾은 큐와 sea를 찾은 큐 두 가지를 운용하자!

 

이 역시 시간초과가 발생했다.

 

틀린 코드 보기

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

def bfs(x, y, w, h):
    cnt = 0
    landq = deque()
    seaq = deque()
    if data[x][y] == 1:
        landq.append((x, y))
    else:
        seaq.append((x, y))
    
    visit = [ [0] * w for _ in range(h)]
    
    dx = [-1, -1, 0, 1, 1, 1, 0, -1]
    dy = [0, 1, 1, 1, 0, -1, -1, -1]
    
    while landq or seaq:
        while landq:
            now_x, now_y = landq.popleft()
            if visit[now_x][now_y] < 2:
                visit[now_x][now_y] = 2
                for i in range(8):
                    nx = now_x + dx[i]
                    ny = now_y + dy[i]
                    if 0 <= nx < h and 0 <= ny < w:
                        if visit[nx][ny] == 0:
                            if data[nx][ny] == 1:
                                landq.append((nx, ny))
                                visit[nx][ny] = 1
                            else:
                                seaq.append((nx, ny))
                                visit[nx][ny] = 1
                    if i == 7 and len(landq) == 0:
                        cnt += 1
        while seaq:
            now_x, now_y = seaq.popleft()
            if visit[now_x][now_y] < 2:
                visit[now_x][now_y] = 2
                for i in range(8):
                    nx = now_x + dx[i]
                    ny = now_y + dy[i]
                    if 0 <= nx < h and 0 <= ny < w:
                        if visit[nx][ny] == 0:
                            if data[nx][ny] == 1:
                                landq.append((nx, ny))
                                visit[nx][ny] = 1
                            else:
                                seaq.append((nx, ny))
                                visit[nx][ny] = 1
    return cnt
            

while True:
    w, h = map(int, input().split())
    if w == 0:
        break
    data = []
    for _ in range(h):
        data.append(list(map(int, input().split())))
    
    cnt = bfs(0, 0, w, h)
    print(cnt)

---

4. 도저히 모르겠다 검색

 

결국 해답을 못 찾고 검색을 하였다.

 

찾으면서 순회하는 나와는 다르게

 

처음부터 순회하며 land(1)만 찾아내는 방식으로 접근하면 코드도 간결하고 아주 쉬워질 수 있었다.

 

하지만 그래도 시간 초과가 발생했다.

 

틀린 코드 보기

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

def bfs(x, y):
    cnt = 0
    q = deque()
    q.append((x, y))
    
    dx = [-1, -1, 0, 1, 1, 1, 0, -1]
    dy = [0, 1, 1, 1, 0, -1, -1, -1]
    while q:
        now_x, now_y = q.popleft()
        visit[now_x][now_y] = 1
        for i in range(8):
            nx = now_x + dx[i]
            ny = now_y + dy[i]
            if 0 <= nx < h and 0 <= ny < w:
                if visit[nx][ny] == 0 and data[nx][ny] == 1:
                    q.append((nx, ny))
            

while True:
    w, h = map(int, input().split())
    if w == 0:
        break
    data = []
    for _ in range(h):
        data.append(list(map(int, input().split())))
    visit = [ [0] * w for _ in range(h)]
    
    cnt = 0
    
    for i in range(h):
        for j in range(w):
            if data[i][j] == 1 and visit[i][j] == 0:
                cnt += 1
                bfs(i, j)
    print(cnt)

---

5. 드디어 정답 코드

 

이 코드 또한 결국 검색해서 찾았다.

 

해결 방법은 visit을 쓰지 않고 이미 탐색한 land를 0으로 바꿔주는 것이다.

 

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

def bfs(x, y):
    q = deque()
    q.append((x, y))
    
    dx = [-1, -1, 0, 1, 1, 1, 0, -1]
    dy = [0, 1, 1, 1, 0, -1, -1, -1]
    while q:
        now_x, now_y = q.popleft()
        data[now_x][now_y] = 0
        for i in range(8):
            nx = now_x + dx[i]
            ny = now_y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and  data[nx][ny] == 1:
                q.append((nx, ny))
                data[nx][ny] = 0
            

while True:
    w, h = map(int, input().split())
    if w == 0:
        break
    data = []
    for _ in range(h):
        data.append(list(map(int, input().split())))
    
    cnt = 0
    
    for i in range(h):
        for j in range(w):
            if data[i][j] == 1:
                cnt += 1
                bfs(i, j)
    print(cnt)

난 이 문제가 visit 배열을 관리하기도 힘들 만큼 빡빡한 문제일 것이라곤 상상도 하지 못했다.

 

너무 어이가 없지만 내 실력인걸..