[백준 1724번] 그림판(파이썬)

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

1724번: 그림판

체감난이도가 높았습니다.

구역을 bfs해주는 건 쉽습니다.

그런데, 이건 선분이 잇는것도 봐야해서

상당히 까다롭습니다.

일반적으로 bfs를 구할 때에는

도행의 한 구역을 기준으로 잡고 구합니다.

그런데 입력받는 건 선분 하나 하나 입니다.

한참 생각하다가 나온 풀이방법.

면을 움직일 때

테두리가 연결되었는지 확인하는 방법입니다.

그림에서 (1,1)에서 움직인다 가정하면

빨간색으로 칠한 부분이

이어져있는지 확인하면 됩니다.

예를들여 위로 간다면

(1,1)과 (1,2)좌표가 연결되어있는지 보면 됩니다.

#백준 1724번 그림판
from collections import deque

dir=[[-1,0],[0,-1],[1,0],[0,1]]

N,M=map(int,input().split())
T=int(input())
#road안을 set으로 둬도 상관없습니다. 
road=[[[]for _ in range(M+1)] for _ in range(N+1)]
visited=[[False]*M for _ in range(N)]

for i in range(T):
    sx,sy,ex,ey=map(int,input().split())
    #세로 줄을 긋는 경우
    if sy==ey:
        start=min(sx,ex)
        end=max(sx,ex)
        for i in range(start,end+1):
            road[i][sy].append(1)
    #가로로 줄을 긋는 경우
    if sx==ex:
        start=min(sy,ey)
        end=max(sy,ey)
        for i in range(start,end+1):
            road[sx][i].append(2)

min_b=1e9
max_b=0



def bfs(x,y):
    q=deque()
    q.append([x,y])
    tmp_cnt=1
    visited[x][y]=True

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

        for d in range(4):
            nx=x+dir[d][0]
            ny=y+dir[d][1]

            if nx<0 or nx>=N or ny<0 or ny>=M:
                continue
            if visited[nx][ny]==True:
                continue
            #위
            if d==0 and (2 in road[x][y] and 2 in road [x][y+1]):
                continue
            #아래
            elif d==2 and (2 in road[x+1][y] and 2 in road[x+1][y+1]):
                continue
            #좌
            elif d==1 and (1 in road[x][y] and 1 in road[x+1][y]):
                continue
            #우
            elif d==3 and (1 in road[x][y+1] and 1 in road[x+1][y+1]):
                continue


            q.append([nx,ny])
            visited[nx][ny]=True
            tmp_cnt+=1

    return tmp_cnt

for x in range(N):
    for y in range(M):
        if visited[x][y]==False:
            cnt=bfs(x,y)
            min_b=min(min_b,cnt)
            max_b=max(max_b,cnt)
print(max_b)
print(min_b)

 

선이 주어질 때 어떻게 BFS를 해야하는지

공부할 수 있는 좋은 문제입니다.

좌표평면에 대한 사고를 넓히기 좋은 문제입니다.