[Gold II] 불켜기 - 11967

문제 링크

성능 요약

메모리: 35464 KB, 시간: 112 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

문제 설명

농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.

베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다.

베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.

입력

첫 번째 줄에는 N(2 ≤ N ≤ 100)과, M(1 ≤ M ≤ 20,000)이 정수로 주어진다.

다음 M줄에는 네 개의 정수 x, y, a, b가 주어진다. (x, y)방에서 (a, b)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다.

출력

베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오.

---

풀이

아이디어 1

1. 우선 모든 방을 완전탐색하며 연결된 방의 불을 켠다.
2. (1, 1)을 Parent로 하는 트리를 만들어 분리집합을 생성한다.
3. 해당 트리에 연결된 노드의 수를 센다

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    x = find(x)
    y = find(y)
    if x > y:
        parent[x] = y
    else:
        parent[y] = x

n, m = map(int, input().split())
parent = [i for i in range(n*m + 1)]
info = []
numbering = lambda x, y: m * (x - 1) + y
for i in range(m):
    info.append(list(map(int, input().split())))

info.sort()

for x, y, dx, dy in info:
    union(numbering(x,y), numbering(dx,dy))
result = 0
for r in parent:
    if r == 1:
        result += 1
print(result)

우선 위 코드에서 간과한게 있다. (또 문제를 마음대로 읽어버렸다.) 문제에서 요구하는것은 "베시가 불을 켤 수 있는 방의 최대 개수를 구하시오." 였지만, 위 코드대로라면, 불을 켤 수 있는 것 중 방향 상관없이 (1, 1)과 연결된 방의 개수를 구하는 것과 같다.
아래 테스트 케이스가 그것을 보여준다.

3 3
1 1 3 3
2 1 1 1
2 2 2 3

위와 같은 그림으로 (1, 1)에서 시작한다면 갈 수 있는 방은 (3, 3)뿐이므로, 총 2가 되어야 한다. 그러나 분리집합만을 사용한다면 아래의 경우가 모두 포함된다.

따라서 여기에 방향의 유향성을 고려해본 코드로 수정을 해보기로 했다.
즉, (1, 1) $\to$(2, 1) $\neq$ (2, 1) $\to$(1, 1)이라는 것이다. 그런데 아무리 생각해봐도 bfs를 사용해서 모든 경로를 탐색하고, 분리집합에서 빼주는 방법 외에는 생각이 잘 나지 않았다. (그러면서 굳이 분리집합을 써야하나..? 이런생각도 들기도 하고,,)

그래서 과감하게 분리집합을 빼기로 했다.

아이디어 2

그러면 어떻게 할 것인가?
우선 1,1부터 방문한 뒤 불을 켤 수 있는 곳은 모두 켠 뒤, result에 추가한다.
사방을 검사하면서 이동할 수 있는 곳의 불을 켠뒤 앞선 과정을 반복한다.

또한 다른 생각은 내가 있는 현재 위치에서 사방을 조사하는 것이 아니라, 내가 있는 위치에 있는 방에서 불을 켤 수 있는 방의 사방을 조사하여 사방의 분리집합이 (1, 1)과 연결되어있는지 확인하는 방법이다. (Disjoint Set 집착중..)
일단 한번 해보기로 했다.

for x, y, dx, dy in info:
    union(numbering(x,y), numbering(dx,dy))

앞선 코드에서 24번째줄인 이 부분만 고치면 될 것 같아서 시도해보기로 했다.

코드를 짜다보니 굳이 분리집합을 사용하지 않는것이 더 간단할 것 같아 중간에 방향성을 조금 바꿨다.

from collections import deque
n, m = map(int, input().split())

connection = [[[] for _ in range(m+1)] for  _ in range(n+1)]
graph = [[0] * (m+1) for  _ in range(n+1)]
visited = [[0] * (m+1) for  _ in range(n+1)]
graph[1][1] = 1

for i in range(m):
    x, y, dx, dy = map(int, input().split())
    connection[x][y].append((dx, dy))

def bfs(x, y):
    q = deque([[x, y]])

    dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
    while q:
        cx, cy = q.popleft()
        visited[cx][cy] = 1
        for con_x, con_y in connection[cx][cy]:
            graph[con_x][con_y] = 1
            q.append([con_x, con_y])


bfs(1, 1)
print(sum(sum(graph, [])))

이번에는 시간초과가 발생하였다. 아무래도 2차원 리스트를 1차원으로 바꾼 뒤 sum함수를 이용하는 부분 때문인것 같은데, 이를 해결하기 위해서 붙어있는 부분을 또다시 BFS로 찾아내는 방법을 사용해보기로 했다. (Pypy로 돌리면 메모리 초과가 발생하므로 이또한 해결해야 한다. -> connection 이 문제일것이다.)

connection의 자료형은 리스트인데 collection모듈의 defaultdict을 사용하면 초기형태가 list인 딕셔너리를 사용할 수 있다. 이를 이용해보고자 한다.

또하나의 특성을 추가하자면, 불켜진 곳의 인근이 불이 켜져있다면 다시 큐에 넣어 재방문 하도록 해야한다.
이를 구현한것이 아래 코드이다.

from collections import deque, defaultdict
import sys
input = sys.stdin.readline

n, m = map(int, input().split())

connection = defaultdict(list)
graph = [[0] * (m+1) for  _ in range(n+1)]
visited = [[0] * (m+1) for  _ in range(n+1)]
graph[1][1] = 1

for i in range(m):
    x, y, dx, dy = map(int, input().split())
    connection[(x, y)].append((dx, dy))


def bfs(x, y):
    result = 1
    q = deque([[x, y]])

    dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
    while q:
        cx, cy = q.popleft()
        for con_x, con_y in connection[(cx, cy)]:
            if not graph[con_x][con_y]:
                graph[con_x][con_y] = 1
                result += 1
            
                for i in range(4):
                    nx, ny = cx + dx[i], cy+dy[i]
                    if (0 < nx < n and 0 < ny < m) and visited[nx][ny]:
                        q.append([nx, ny])
        
        for i in range(4):
            nx, ny = cx + dx[i], cy+dy[i]
            if 0 < nx < n and 0 < ny < m:
                if not visited[nx][ny] and graph[nx][ny]:
                    q.append([nx, ny])
                    visited[nx][ny] = 1
    
    return result


print(bfs(1, 1))

불켜고 재방문 하는 코드를 짜는 부분에서 실수가 있었고 최종 코드는 아래 코드이다.

코드

from collections import deque, defaultdict
import sys
input = sys.stdin.readline

n, m = map(int, input().split())

connection = defaultdict(list)
graph = [[0] * (m+1) for  _ in range(n+1)]
visited = [[0] * (m+1) for  _ in range(n+1)]
graph[1][1] = 1

for i in range(m):
    x, y, dx, dy = map(int, input().split())
    connection[(x, y)].append((dx, dy))


def bfs(x, y):
    result = 1
    q = deque([[x, y]])

    dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
    while q:
        cx, cy = q.popleft()
        for con_x, con_y in connection[(cx, cy)]:
            if not graph[con_x][con_y]:
                graph[con_x][con_y] = 1
                result += 1
            
                for i in range(4):
                    nx, ny = con_x + dx[i], con_y+dy[i]
                    if (0 < nx < n and 0 < ny < m) and visited[nx][ny]:
                        q.append([nx, ny])
        
        for i in range(4):
            nx, ny = cx + dx[i], cy+dy[i]
            if 0 < nx < n and 0 < ny < m:
                if not visited[nx][ny] and graph[nx][ny]:
                    q.append([nx, ny])
                    visited[nx][ny] = 1
    
    return result


print(bfs(1, 1))

---

회고

다양한 방법을 많이 생각하려고 했던것 같다. 지금와서 다시보면 그냥 문제만 따라가면서 풀면 오히려 간단했을건데, 문제를 우선 단순한 방법으로 풀기위해 가장 간단한 아이디어부터 실행해 나가는것이 좋을것 같단 생각을 했다.