[백준알고리즘] 3108번: 로고 -Python

[백준알고리즘] 3108번: 로고 -Python

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

3108번: 로고

한 번도 들어본 적 없는 로고라는 언어가 있다고 한다.

 

이 문제는 Union-Find 형식으로 문제를 풀었다. 각각의 직사각형을 Disjoint Set으로 보고, 겹치는 부분이 생긴다면 링크를 주고 헤드를 유지하도록 했다.

서로 다른 Set의 두 직사각형이 만나면 하나의 Set이 하나의 Set 아래로 들어가도록 했다.

 

알고리즘 분류는 DFS, BFS인데 이 방식이 더 쉬운 것 같다. 처음에는 BFS 방식으로 풀었는데, 틀렸어서 현타 왔다가 다 지우고 이 방법으로 풀었다.

 

 

밑에 코드에서 group 리스트가 각각의 상위 gid를 저장하고 있는 리스트로, 서로다른 gid의 두 원소가 만나게 되면 두 원소의 헤드 gid를 비교하게 된다. gid가 같으면 이미 같은 그룹이기 때문에 별다른 처리를 해주지 않고, gid가 다르다면 하나의 Set에 다른 하나의 Set이 포함될 수 있도록 헤드 h2가 헤드 h1을 가리키도록 해주었다.

 

그리고 마지막에 헤드의 총 개수를 세주었다.

 

여기서 거북이는 (0, 0)에서 출발을 하며 연필을 내린 상태에서 시작하기 때문에 (0, 0)을 방문하지 않았다면 한 번 더 PU과정을 해주어야 하기 때문에 그룹의 개수가 (0, 0)을 방문한 경우보다 PU의 횟수가 하나 많다는 것을 생각해 마지막에 처리를 해주었다.

코드 상에서는 반대로 (0, 0)을 방문했다면 Set의 개수에서 1을 감소시켰다.

import sys

n = int(sys.stdin.readline())
position = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
group = [0] * 1001
gid = 0
visit = {}

def change(g1, g2):
    h1, h2 = g1, g2
    while h1 != group[h1]:
        h1 = group[h1]
    while h2 != group[h2]:
        h2 = group[h2]
    if h1 == h2: return
    else: group[h2] = h1
    
for x1, y1, x2, y2 in position:
    gid += 1
    group[gid] = gid
    for i in range(y1, y2+1):
        if visit.get((i, x1)):
            change(gid, visit[(i, x1)])
        if visit.get((i, x2)):
            change(gid, visit[(i, x2)])
        visit[(i, x1)] = gid
        visit[(i, x2)] = gid
    for j in range(x1+1, x2):
        if visit.get((y1, j)):
            change(gid, visit[(y1, j)])
        if visit.get((y2, j)):
            change(gid, visit[(y2, j)])
        visit[(y1, j)] = gid
        visit[(y2, j)] = gid
        
cnt = 0
for i in range(1, 1001):
    if i == group[i]:
        cnt += 1
        
if visit.get((0, 0)):
    cnt = cnt-1 if cnt > 0 else 0
print(cnt)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다