[BOJ] 3108 / 로고 / Python 파이썬

[BOJ] 3108 / 로고 / Python 파이썬

[BOJ] 3108 / 로고 / Python 파이썬

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

3108번: 로고

 

풀이

인접한 사각형끼리의 구분을 짓는것과 는 시간초과를 해결해야 하는 그래프 문제이다.

 

인접한 사각형의 경우는 경로가 이어져 있지 않지만 사각형 두개가 매우 인접해 있다면, 같은 그래프 경로로 판단되었다.

이를 해결하기 위해 주어진 모든 좌표를 -500~500 에서 0~2000 으로 만들어 주어 해결하였다.

 

시간초과를 해결하는 것에서 꽤나 애를 먹었는데,

모든 범위를 탐색하여 경로의 개수를 파악하는 것에서 경로를 시작하는 점들로 탐색의 시작범위를 줄이니 해결되었다.

 

from collections import deque

N = int(input())

maps = [[0 for _ in range(2001)] for _ in range(2001)]
startingQue = deque()

for _ in range(N):
    x1, y1, x2, y2 = map(int, input().split())

    x1 = (x1 + 500) * 2
    y1 = (y1 + 500) * 2
    x2 = (x2 + 500) * 2
    y2 = (y2 + 500) * 2

    for i in range(x1, x2+1):
        maps[y1][i] = 1
        maps[y2][i] = 1

    for i in range(y1, y2+1):
        maps[i][x1] = 1
        maps[i][x2] = 1
    startingQue.append((y1, x1))

startingQue.append((1000, 1000))


dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
visited = [[0 for _ in range(2001)] for _ in range(2001)]
res = 0

for q in startingQue:
    if visited[q[0]][q[1]]:
        continue

    res += 1
    queue = deque()
    queue.append(q)
    while queue:
        qY, qX = queue.popleft()

        if visited[qY][qX]:
            continue

        visited[qY][qX] = 1

        for i in range(4):
            Y = qY + dy[i]
            X = qX + dx[i]

            if 0 <= Y <= 2000 and 0 <= X <= 2000:
                if maps[Y][X] and not visited[Y][X]:
                    queue.append((Y, X))

print(res-1)