[백준] 그림

문제

백준 그림 https://www.acmicpc.net/problem/1926

 

코드

from collections import deque

n, m = map(int, input().split())    # 세로, 가로
paper = [list(map(int, input().split())) for _ in range(n)]

visit = [[False for _ in range(m)] for _ in range(n)]   # 방문 기록용
maxi = 0
picture_count = 0

for i in range(n):  # 세로좌표
    for j in range(m):  # 가로좌표
        if paper[i][j] == 1 and visit[i][j] == False:   # 그림이고, 방문한적 없다면
            picture_count += 1
            
            # bfs
            q = deque()
            q.append([i, j])
            visit[i][j] = True
            area = 1

            while q:
                ey, ex = q.popleft()

                # 4방향 탐색
                for dy,dx in [0, 1], [0, -1], [1, 0], [-1, 0]:  #우, 좌, 하, 상
                    ny = ey + dy    # 갈곳의 y 좌표
                    nx = ex + dx    # 갈곳의 x 좌표

                    if 0 <= ny < n and 0 <= nx < m:     # 갈곳이 종이 범위 안이라면
                        if paper[ny][nx] == 1:          # 갈곳이 그림이라면
                            if not visit[ny][nx]:       # 갈곳에 방문한적 없다면
                                visit[ny][nx] = True
                                area += 1
                                q.append([ny,nx])

            maxi = max(maxi, area)

print(picture_count)
print(maxi)

 

풀이

n, m = map(int, input().split())    # 세로, 가로
paper = [list(map(int, input().split())) for _ in range(n)]

visit = [[False for _ in range(m)] for _ in range(n)]   # 방문 기록용
maxi = 0
picture_count = 0

입력조건에 맞춰서 n, m, paper 변수를 입력받는다.

 

visit는 bfs 실행시 해당 좌표를 방문했는지 안했는지 판별하기 위해 쓰이는 배열이다.

maxi는 가장 넓은 그림의 넓이가 될 출력값 변수다.

picture은 최종적으로 그림의 개수가 될 출력값 변수다.

 

for i in range(n):  # 세로좌표
    for j in range(m):  # 가로좌표
        if paper[i][j] == 1 and visit[i][j] == False:   # 그림이고, 방문한적 없다면
            picture_count += 1

종이의 각 좌표를 모두 탐색한다.

해당 좌표가 그림부분이고, 방문한적이 없다면, 그림의 개수를 += 1 하고, bfs를 실행해서 그림의 넓이를 구한다.

 

# bfs
q = deque()
q.append([i, j])
visit[i][j] = True
area = 1

while q:
    ey, ex = q.popleft()

    # 4방향 탐색
    for dy,dx in [0, 1], [0, -1], [1, 0], [-1, 0]:  #우, 좌, 하, 상
        ny = ey + dy    # 갈곳의 y 좌표
        nx = ex + dx    # 갈곳의 x 좌표

        if 0 <= ny < n and 0 <= nx < m:     # 갈곳이 종이 범위 안이라면
            if paper[ny][nx] == 1:          # 갈곳이 그림이라면
                if not visit[ny][nx]:       # 갈곳에 방문한적 없다면
                    visit[ny][nx] = True
                    area += 1
                    q.append([ny,nx])

maxi = max(maxi, area)

bfs를 실행하기전에 초기화 작업을 한다.

큐를 생성하고, 현재 좌표를 큐에 넣는다.

현재좌표는 방문처리하고, 그림의 넓이가 될 변수를 1로 초기화한다.

 

큐에 쌓인 좌표가 없을때까지 bfs를 반복한다.

bfs에서 현재좌표는 큐에서 하나씩 꺼내올것이다.

큐에서 꺼낸 현재 좌표를 기준으로 다음으로 갈 좌표 상하좌우를 탐색하며

다음으로 갈 좌표가 종의 범위 안이고, 그림이고, 방문한적 없다면

다음으로 갈 좌표를 방문처리하고, 넓이를 1 늘리고, 큐에 다음으로 갈 좌표를 넣는다.

 

bfs가 끝났으면 maxi에 그림넓이의 최대값을 업데이트한다.

 

새롭게 배운점 / 느낀점

• bfs 개념은 알고있지만, 손으로 직접 구현할때마다 하나씩 헷갈리는 부분이 있는것 같다. 
• 많은 bfs문제를 풀며 구현에 익숙해 지는 연습이 필요할것같다.

 

 

더 나은 의견이나 궁금하신게 있다면 편하게 댓글 달아주세요 :)