백준(BOJ) 1724 그림판(Python)

문제 내용

 

BFS로 풀 수 있었던 문제.

일반적인 BFS 문제와는 달리 벽을 생성해야 하는 문제였다.

컴실1 maze project에서 이와 비슷한 유형의 자료구조를 구현해봤기 때문에 쉽게 풀 수 있었다.

2차원 리스트의 각 칸을 하나의 픽셀로 생각하고, 그 픽셀의 상, 하, 좌, 우 방향으로 이동할 수 있는지를 체크해줬다.

처음에는 모두 이동할 수 있도록 초기화하고, 가장자리 픽셀에서 리스트 밖으로는 벗어나지 못하도록 한 뒤 선분을 입력받는다.

입력받은 선분이 리스트의 가장자리에 위치한다면 pass하고, 그렇지 않은 경우 두 점의 x좌표가 동일하다면 x좌표를 기준으로 변화하는 y좌표에 대해 해당하는 선분의 위 픽셀은 아래로 이동할 수 없고, 아래 픽셀은 위로 이동할 수 없도록 설정한다. y좌표는 x좌표와 마찬가지로 해주면 된다.

그 후에는 BFS를 진행하되, 해당 픽셀에서 이동할 수 있는 방향으로만 이동하며 BFS를 진행하며 조각의 크기를 측정한다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

n,m=map(int,input().split())
t=int(input())
L=[[[1,1,1,1] for i in range(m)] for j in range(n)]
visited=[[0 for i in range(m)] for j in range(n)]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
Maximum=0
minimum=10e9
for i in range(n):
    for j in range(m):
        if i==0:
            L[i][j][0]=0
        elif i==n-1:
            L[i][j][1]=0
        if j==0:
            L[i][j][2]=0
        elif j==m-1:
            L[i][j][3]=0
for i in range(t):
    x1,y1,x2,y2=map(int,input().split())
    if x1==x2==0 or x1==x2==n or y1==y2==0 or y1==y2==m:
        continue
    if x1==x2:
        p=min(y1,y2)
        for j in range(abs(y2-y1)):
            L[x1][p+j][0]=0
            L[x1-1][p+j][1]=0
    elif y1==y2:
        p=min(x1,x2)
        for j in range(abs(x2-x1)):
            L[p+j][y1][2]=0
            L[p+j][y1-1][3]=0

for i in range(n):
    for j in range(m):
        if not visited[i][j]:
            queue=deque()
            queue.append([i,j])
            visited[i][j]=1
            c=0
            while queue:
                x,y=queue.popleft()
                c+=1
                for k in range(4):
                    nx=x+dx[k]
                    ny=y+dy[k]
                    if 0<=nx<n and 0<=ny<m and L[x][y][k] and not visited[nx][ny]:
                        queue.append([nx,ny])
                        visited[nx][ny]=1
            Maximum=max(c,Maximum)
            minimum=min(c,minimum)
print(Maximum)
print(minimum)

 

BFS 코드를 짤 때 습관적으로 queue에 다 집어넣고 뽑아서 visited를 확인했는데, 그렇게 하니 메모리 초과가 터졌다.

어찌보면 당연한데, 중복되는 좌표가 queue에 여럿 push되기 때문에 메모리 초과가 발생하는 것이다.

따라서 처음부터 queue에 push할 때 visited를 확인해주니 통과했다.

조심해야 할 것 같다.