[Python/코테] 백준 1926 그림

1926 그림

문제 및 조건 설명: https://www.acmicpc.net/problem/1926

 

알고리즘 설계

1. 하나의 경로를 끝까지 파는 경우(dfs)가 아니라, 연결된 공간의 너비를 구하는 경우(bfs)이므로 BFS 알고리즘을 사용해 그림을 탐색한다.
2. 그림이 몇 개인지, 가장 넓은 그림이 무엇인지를 출력해야 한다.
   1. 그림의 너비를 판단하기 위해 시작 좌표에서부터 BFS를 실행하고, 탐색하는 과정에서 접근 가능한 좌표 당 너비 변수 1을 증가시킨다.
   2. 그림의 갯수를 판단하기 위해 전체 공간의 좌표 중, 방문하지 않은 경우 BFS를 실행하도록 한다.
   3. 그림의 최대 너비를 판단하기 위해 그림 너비를 구할 때마다 최대값과 비교해준다.

정답 코드

from collections import deque

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

cnt = 0
ans = 0


def bfs(x, y):
    a[x][y] = 0
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    width = 1

    queue = deque()
    queue.append((x, y))

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

        for i in range(4):
            nx = dx[i] + x
            ny = dy[i]+y
            if 0 <= nx < n and 0 <= ny < m and a[nx][ny] == 1:
                queue.append((nx, ny))  # queue에 삽입
                a[nx][ny] = 0   # 방문 표시
                width += 1

    return width


for i in range(n):
    for j in range(m):
        if a[i][j] == 1:
            cnt += 1
            ans = max(bfs(i, j), ans)

print(cnt)
print(ans)

코드 출처: https://velog.io/@y7y1h13/알고리즘백준-1926번-그림python

나다어

• 기본 BFS 함수 구조를 외우자.
• 안 외워진다면..

1. 큐에 저장되고, 큐가 다 비워지면 끝난다.
2. 시작 좌표의 방문 표시를 잊지 마라.
3. 시작 좌표를 큐에 넣으며 탐색이 시작된다.
4. 상하좌우 좌표를 반복 탐색한다.
   1. 큐에서 해당 좌표를 popleft 한다.
   2. 행(x), 열(y) 좌표를 업데이트하고, 범위를 벗어나지 않는지 확인한다.
   3. 큐에 새로운 좌표를 append한다.
   4. 큐에 넣은 좌표의 방문 표시를 한다.

문법 *나다어

*나는 다음에 어떻게 풀 것인가

 

2차원 배열 선언하기

arr = [[0 for j in range(cols)] for i in range(rows)]

2차원 배열로 입력받기

arr = [list(map(int, input().split())) for _ in range(n)]