백준 4963 섬의 개수, 1926 그림

4963 섬의 개수

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다.

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

섬의 개수를 세는 프로그램을 작성하시오.

'''
input = 
    1 1			=>  너비 w와 높이 h
    0
    2 2
    0 1
    1 0
    3 2
    1 1 1
    1 1 1
    5 4
    1 0 1 0 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 1 0
'''

from collections import deque

dx = [0, 0, 1, -1, -1, 1, 1, -1] # 우 좌 하 상 우상 좌하 우하 좌상
dy = [1, -1, 0, 0, 1, -1, 1, -1]   

def bfs(a, b):
    queue = deque()
    queue.append((a, b))
    visit[a][b] = True

    while queue:
        x, y = queue.popleft()      

        for i in range(8):  # 이동 역할
            nx = x + dx[i]  
            ny = y + dy[i] 

            if 0 <= nx < m and 0 <= ny < n and not visit[nx][ny]:
                if maps[nx][ny] == 1:
                    visit[nx][ny] = True
                    queue.append((nx, ny))          

while True:
    n ,m = map(int, input().split())        # 넓이 == 열, 높이 == 행

    if n == 0 and m == 0:       
        break

    maps = [list(map(int, input().split())) for _ in range(m)]
    visit = [[False] * n for _ in range(m)]
    land = 0

    for i in range(m):          # 행
        for j in range(n):      # 열
            if maps[i][j] == 1 and not visit[i][j]:
                bfs(i, j)
                land += 1
    print(land)

BFS를 바탕으로  가로, 세로, 대각선 8방향을 탐색하며 섬을 나타내는 1의 값을 찾는다. 

8방향으로 1을 탐색하며 연속적으로 1이 나오는 경우 이를 한 묶음(섬)으로 보고 섬의 개수를 카운트한다. 

 

 

dx = [0, 0, 1, -1, -1, 1, 1, -1] # 우 좌 하 상 우상 좌하 우하 좌상
dy = [1, -1, 0, 0, 1, -1, 1, -1]   # 0, 1 / -1, 1

dx, dy에 8방향으로 탐색할 이동 좌표의 값을 리스트로 만들어준다. 

 

while True:
    n ,m = map(int, input().split())        # 넓이 == 열, 높이 == 행

    if n == 0 and m == 0:       
        break

    maps = [list(map(int, input().split())) for _ in range(m)]
    visit = [[False] * n for _ in range(m)]
    land = 0

    for i in range(m):          # 행
        for j in range(n):      # 열
            if maps[i][j] == 1 and not visit[i][j]:
                bfs(i, j)
                land += 1

n과 m으로 입력값을 받는다. 이때 n은 열, m은 행의 값을 받는다. 

 

입력값 중 '0 0' 의 값이 나올 시 입력값을 받는 것을 중단한다. 

 

maps의 이름으로 섬의 위치를 나타낼 metrix와 방문 처리 리스트를 만든다. 

 

이중 for문으로 현재 위치를 바꿔주며 1을 탐색한다. 

이때 조건문을 통해 섬의 위치를 나타내는 1을 탐색하고, 방문처리 되지 않은 좌표를 찾는다. 

위의 조건을 충족한다면 bfs에 좌표값을 넣어주며 해당 좌표의 위치로 이동한다. 

 

 while queue:
        x, y = queue.popleft()     

        for i in range(8):  # 이동역할1
            nx = x + dx[i]  # nx = 0
            ny = y + dy[i]  # ny = 1

            if 0 <= nx < m and 0 <= ny < n and not visit[nx][ny]:
                if maps[nx][ny] == 1:
                    visit[nx][ny] = True
                    queue.append((nx, ny))

queue에서 제거된 값은 현재 위치를 나타내는 x, y의 위치가 된다. 

 

for문을 통해 8방향으로 이동하며 탐색할 dx, dy의 좌표 위치를 new x, new y를 뜻하는 nx, ny에 넣어준다. 

이때 8방향을 탐색해야 하므로 range에 8을 넣어주어야 한다. 

 

탐색 시 조건은

1. 탐색할 방향의 위치가 모든 좌표의 범위를 벗어나지 않는다.
2. 방문 처리 되지 않은 곳이다. 
3. 이동할 좌표의 값이 1이다. 

이 조건들을 모두 충족한다면 방문 처리 후, queue에 해당 좌표의 값을 넣어줌으로써 해당 좌표로 이동한다.

 

위 구문들을 반복하여 8방향을 모두 탐색했다면, 

    for i in range(m):          # 행
        for j in range(n):      # 열
            if maps[i][j] == 1 and not visit[i][j]:
                bfs(i, j)
                land += 1
    print(land)

해당 구문으로 돌아와 연속된 1을 8방향으로 성공적으로 탐색했다면 land에 1을 더해주어 섬의 개수를 카운트한다. 

 

 

1926 그림

어떤 큰 도화지에 그림의 개수와, 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라.

단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자.

가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다.

그림의 넓이란 그림에 포함된 1의 개수이다.

'''
input =
    6 5
    1 1 0 1 1
    0 1 1 0 0
    0 0 0 0 0
    1 0 1 1 1
    0 0 1 1 1
    0 0 1 1 1
'''

from collections import deque

dx = [0, 0, 1, -1]	# 우 좌 하 상
dy = [1, -1, 0, 0]

def bfs(a, b):
    queue = deque()
    queue.append((a, b))
    visit[a][b] = True
    cnt = 1

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and not visit[nx][ny]:
                if maps[nx][ny] == 1:
                    cnt += 1
                    visit[nx][ny] = True
                    queue.append((nx, ny))
    return cnt
n ,m = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
visit = [[False] * m for _ in range(n)]
land = 0

answer = []
for i in range(n):
    for j in range(m):
        if maps[i][j] == 1 and not visit[i][j]:
            answer.append(bfs(i, j))
            land += 1
print(land)
print(max(answer))

섬의 개수와 같은 개념으로 연속된 1을 찾아 이를 한 묶음으로 보고 그림의 개수를 찾는다. 

이때 대각선은 떨어진 그림이므로 4방향으로 1을 탐색한다. 

 

 

탐색 방식은 섬의 개수와 같으며, 

for i in range(n):
    for j in range(m):
        if maps[i][j] == 1 and not visit[i][j]:
            answer.append(bfs(i, j))
            land += 1

가장 넓은 그림의 넓이를 구해야하기 때문에, 하나로 묶여진 그림을 탐색할 때 연속된 1의 개수 또한 동시에 구한다. 

현재 위치가 1이고, 방문처리 되지 않은 곳을 탐색하며 bfs(i, j)의 1의 값은 answer에 넣어준다. 

추후 max(answer)로 1이 가장 많은 묶음 (가장 넓은) 값을 출력한다.