[Python][백준/BOJ] 1926번 : 그림

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

1926번: 그림

 

내 코드

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

n,m = map(int, input().split())
image = [list(map(int, input().split())) for i in range(n)]
visited =[[False]*m for _ in range(n)]
cnt =0
dx = [1,-1, 0,0]
dy = [0,0,1,-1]

def bfs(x, y):
    width =1
    q = deque()
    q.append((x,y))
    visited[x][y] = True
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m:
                if image[nx][ny]==1 and not visited[nx][ny]:
                    visited[nx][ny] =True
                    q.append((nx, ny))
                    width +=1
    return width

ans = 0
for i in range(n):
    for j in range(m):
        if image[i][j] == 1 and not visited[i][j]:
            cnt +=1
            ans = max(bfs(i,j), ans)
            
print(cnt)
print(ans)

 

코드 리뷰

아직 어느 상황에 DFS를 사용하고, BFS를 사용하는지 능숙하지 않은 것 같다.

이 문제도 처음에 그림 하나를 타고 너비를 파악하기 위해 깊숙히 들어가야 한다는 점에서 DFS라고 생각했다.

하지만 문제 자체를 보았을 때 전체 도화지를 다 돌면서, 그림의 너비와 개수가 몇 개인지를 요구하고 있기 때문에 BFS를 사용하는 것이 맞았다.

전체를 다 도는 경우는 BFS라는 것을 명심하자!

 

BFS

def bfs(x, y):
    width =1
    q = deque()
    q.append((x,y))
    visited[x][y] = True
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m:
                if image[nx][ny]==1 and not visited[nx][ny]:
                    visited[nx][ny] =True
                    q.append((nx, ny))
                    width +=1
    return width

q에 현재 좌표에 해당하는 x, y를 넣어주며 한 바퀴 돌릴 것이다.

상하좌우로 움직이면서, 만약 도화지에 1이라고 표시가 되어있으면서 방문하지 않은 곳을 방문할 것이다.

방문했으면 체크해주고, q에 추가해주면 된다. 그리고 추가하는 것과 동시에 너비도 1씩 더 체크해주면 된다.

함수는 너비를 알기 위해 돌리는 것이기 때문에, q 한 바퀴를 모두 돌고 나서 너비를 반환해준다.

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

그리고 전체적으로 도화지 한 바퀴를 돌면서 체크하기 위해서 해당 for문을 사용한다.

도화지가 1이면서 방문하지 않은 곳을 시작점으로 두고, bfs함수에 넣어준다.

• cnt : 총 몇 번 돌았는지 = 그림의 개수
• ans : 무엇이 제일 큰지 = 가장 넓은 너비