[BOJ/백준] 3108 로고 파이썬

문제 링크 : https://www.acmicpc.net/problem/3108

3108번: 로고

 

BFS로 풀이 했다.

 

문제를 정리하면 한붓 그리기를 위해선 붓을 맵에 놓아야하는데 이때 붓을 몇번 놓는지 구하면 된다.

 

내 풀이의 핵심은 도형의 크기를 두배 확장하는 것이다.

 

나는 BFS를 통해서 한붓그리기가 가능한지 판별한다. 근데 테두리가 겹치는 것만 한붓그리기가 가능하지만 BFS를 수행하면 동서남북으로 인접한 곳을 확인하게 된다. 그러면 사각형안에 사각형이 있는 경우고 가능하다고 판별하게 된다. 그래서 두개 확장한다.

아래의 경우 그렇게 된다.

1 1 1 1 1

1 2 2 2 1

1 2 0 2 1

1 2 2 2 1

1 1 1 1 1

 

그래서 두배 확장하면 아래처럼 경계가 명확해진다.

1 1 1 1 1 1 1 1 1 1

1 0 0 0 0 0 0 0 0 1

1 0 2 2 2 2 2 2 0 1

1 0 2 0 0 0 0 2 0 1

1 0 2 0 0 0 0 2 0 1

1 0 2 0 0 0 0 2 0 1

1 0 2 0 0 0 0 2 0 1

1 0 2 0 0 0 0 2 0 1

1 0 2 2 2 2 2 2 0 1

1 0 0 0 0 0 0 0 0 1

1 1 1 1 1 1 1 1 1 1

 

따라서 배열의 크기가 -500~500 이므로 -1000~1000으로 확장하고 또한 인덱스는 0부터 이므로 0~2000까지 맵의 크기를 정하면 된다.

 

이제 점을 입력받고 맵에 테두리를 그리자.

 

그리고 입력받은 점에서 BFS를 수행하는데 이때 방문체크를 해주자.

다음번에 해당 점을 봤을 때 방문했던 거라면 지나가면 된다.

 

이렇게 해서 총 몇번의 BFS를 도는지 즉 붓을 몇번 내려서 그리기 시작했는지 세주면 된다.

 

그리고 마지막에 시작점에 테두리가 포함됐는지 확인해야한다.

 

문제에 연필을 내린상태에서 시작한다고 나와있다. 즉 붓을 맵에 내려놓기 시작하기 때문에 -1을 해주자.

 

from sys import stdin
from collections import deque

input = stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]
MAX = 2001

n = int(input())

points = [list(map(lambda x:int(x)*2+1000, input().split())) for _ in range(n)]

board = [[0]*MAX for _ in range(MAX)]
def solv():
    set_border()
    visited = [[False]*MAX for _ in range(MAX)]

    answer = 0
    for x1,y1,x2,y2 in points:
        if not visited[x1][y1]:
            bfs(x1,y1,visited)
            answer += 1
    answer += -1 if board[1000][1000] != 0 else 0
    print(answer)
def bfs(sx,sy,visited):
    global board

    q = deque([(sx,sy)])
    visited[sx][sy] = True
    while q:
        x,y = q.pop()

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if point_validator(nx, ny, visited):
                visited[nx][ny] = True
                q.appendleft((nx,ny))

def point_validator(x,y,visited):
    if x < 0 or y < 0 or x >= MAX or y >= MAX:
        return False
    elif board[x][y] == 0:
        return False
    elif visited[x][y]:
        return False
    return True

def set_border():
    global board

    idx = 1
    for x1,y1,x2,y2 in points:
        for y in range(y1,y2+1):
            board[x1][y] = board[x2][y] = idx
        for x in range(x1,x2+1):
            board[x][y1] = board[x][y2] = idx
        idx += 1

solv()