[algorithm] 백준 소가 길을 건너간 이유 6 #14466

해당 블로그는 개인이 공부하고, 정리한 걸 기록하는 공간입니다.
오타, 오류가 존재할 수 있습니다. 댓글을 달아주시면 수정할 수 있도록 하겠습니다.

문제 풀러가기

코드 보기

def param():
    N, K, R = list(map(int, input().split()))
    
    no_move = {}
    for _ in range(R):
        a, b, c, d = list(map(int, input().split()))
        no_move[(a, b)] = no_move.get((a, b), [])
        no_move[(a, b)].append([c, d])

        no_move[(c, d)] = no_move.get((c, d), [])
        no_move[(c, d)].append([a, b])
                
    cows = []
    for _ in range(K):
        cows.append(list(map(int, input().split())))
        
    return N, K, R, no_move, cows
        
def search(cow):
    # 방문 여부
    visited = [[False] * (N+2) for _ in range(N+2)]
    visited[0] = [True] * (N+2)
    visited[-1] = [True] * (N+2)
    
    for x in range(N+2):
        visited[x][0] = True
        visited[x][-1] = True
        
    stack = []
    stack.append(cow)

    while stack:
        point = stack.pop()
            
        # 방문
        visited[point[0]][point[1]] = True

        roads = no_move.get((point[0], point[1]), [])
        
        # 위
        if not visited[point[0] - 1][point[1]] and not [point[0] - 1, point[1]] in roads:
            stack.append([point[0] - 1, point[1]])
        
        # 아래
        if not visited[point[0] + 1][point[1]] and not [point[0] + 1, point[1]] in roads:
            stack.append([point[0] + 1, point[1]])
        
        # 좌
        if not visited[point[0]][point[1] - 1] and not [point[0], point[1] - 1] in roads:
            stack.append([point[0], point[1] - 1])
        
        # 우
        if not visited[point[0]][point[1] + 1] and not [point[0], point[1] + 1] in roads:
            stack.append([point[0], point[1] + 1])
            
    return visited
    

N, K, R, no_move, cows = param()
answer = 0

# 모든 소 돌기
for idx, cow in enumerate(cows):
    # 자기 자신, 이전 소는 제외
    collection = cows[idx + 1::]
    # 소 하나가 갈 수 있는 모든 목초지 (길 제외)
    visited = search(cow)
    
    # 소가 간 곳에 다른 소의 존재 여부를 확인한다. 
    for dest in collection:
        if not visited[dest[0]][dest[1]]:
            answer += 1
        
print(answer)

소가 길을 건너간 이유 6

---

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	297	145	119	50.000%

문제 설명

소가 길을 건너간 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다.

존의 농장에 대대적인 개편이 있었다. 이제 작은 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다.

K마리의 (1 ≤ K ≤ 100,K ≤ N2) 소가 존의 농장에 있고, 각 소는 서로 다른 목초지에 있다. 어떤 두 소는 길을 건너지 않으면 만나지 못 할 수 있다. 이런 소가 몇 쌍인지 세어보자.

입력

첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. 그 다음 K줄에는 한 줄의 하나씩 소의 위치가 행과 열로 주어진다.

출력

길을 건너지 않으면 만날 수 없는 소가 몇 쌍인지 출력한다.

예제 입력 1

3 3 3
2 2 2 3
3 3 3 2
3 3 2 3
3 3
2 2
2 3

예제 출력 1

2

설명 & 구현 방법

---

처음에 문제를 이해하는 게 어려웠다.
문제를 풀어서 다시 이해하면 서로 다른 위치에 있는 소들이 주어진 길(R)을 제외했을 때 만날 수 없는 쌍을 구하는 문제였다.

1. 모든 소(x, y)가 주어진 길(R)를 제외한 모든 곳을 간다.
2. 이때, 자기 자신(소)을 제외한 다른 소에 도달한 적이 있으면 무시, 만약 도달한 적이 없다면 주어진 길로만 도달 가능한 경우이기 때문에 +1을 한다.

처음에 시간 초과가 발생했는데, 그 이유는 시작 소 -> 도착 소의 dfs를 구했다.
이러다 보니 시작소 가 같은 경우 같던 길을 또 가보는 중복이 발생했다.
아마 K!의 시간 복잡도가 발생했다고 예상한다.

시간을 단축하기 위해서 시작 소 기준 dfs를 한번만 실행한 뒤, 시작 소가 방문하지 못한 위치에 다른 소가 존재한 경우를 count 했더니 시간 초과를 해결할 수 있었다.