[백준 14466]소가 길을 건너간 이유6(파이썬,BFS,DFS)

www.acmicpc.net/problem/14466

14466번: 소가 길을 건너간 이유 6

문제

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

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

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

입력

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

출력

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

 

 

###풀이

 

뒤에 6이 붙어있는 것 보니까 1번부터 있는 문제같다. 6번만 풀어서 설명이 조금 많이 난해하다.

문제 이해하는데 오랜 시간이 걸렸다.

문제만 이해하면 단순한 BFS,DFS문제인데.

 

주어지는 길정보 입력을 road_matrix로 저장해서 BFS를 진행할때마다 참고했다.

주어진 소에 대해서 길을 건너지 않는 BFS를 진행하고 만나는 소마다 now_count + 1를 해준다.

그럼 이 소가 만날 수 있는 놈들이 나오는데

전체 소놈들 수에서 만난 소를 빼면 만나지 못하는 소의 숫자가 나온다! 더해주면된다.

 

또한 "쌍"의 수를 구하라고 했다.

이미 체크한 소는 매트릭스(cow_matrix)와 전체 소의 수(cow_number)에서 빼면

이미 체크한 쌍을 다시 추가하는 일이 없어질 것이다.  

 

###피드백

난해해서 쫄았지만 필요한 매트릭스를 전부 만들어서 풀었다.

필요하고 더 단순해진다면 메모리 사용하는 것은 많이 걱정하지말자

소의 쌍을 구하시오나 길에 대한 설명 등 문제를 잘 읽어야한다.

 

 

#https://www.acmicpc.net/problem/14466
from collections import deque

def solution():
    count = 0
    VECTOR = ((1, 0),(-1, 0),(0, 1),(0, -1))

    n, k, r = map(int, input().split())

    cow_matrix = [[0] * n for _ in range(n)]
    road_matrix = [ [ [] for _ in range(n) ] for _ in range(n) ]

    for _ in range(r):
        a, b, c, d = map(int, input().split())
        if road_matrix[a - 1][b - 1] == []:
            #print(road_matrix[a - 1][b - 1]==[])
            road_matrix[a - 1][b - 1] = [ [c-1, d-1] ]
        else:
            road_matrix[a - 1][b - 1].append([c-1, d-1])

        if road_matrix[c - 1][d - 1] == []:
            road_matrix[c - 1][d - 1] = [[a-1, b-1]]
        else:
            road_matrix[c - 1][d - 1].append([a-1, b-1])


    cow_list = list()
    cow_number = 0
    #여기서 EOF에러,,
    for _ in range(k):
        x, y = map(int, input().split())
        cow_matrix[x-1][y-1] = 1
        cow_list.append((x, y))
        cow_number += 1

    def bfs_cow(cow):
        now_count  = 0
        visited_matirx = [[0] * n for _ in range(n)]
        q = deque()
        q.append(cow)

        visited_matirx[cow[0]-1][cow[1]-1] = 1
        while q:

            now_xy = q.popleft()
            now_x = now_xy[0]
            now_y = now_xy[1]
            #print("now소",now_x,now_y)
            for (vec_x, vec_y) in VECTOR:
                #print(now_x -1 + vec_x, now_y -1  + vec_y, road_matrix[now_x-1][now_y-1])

                if 0 <= now_x - 1 + vec_x < n and 0 <= now_y - 1 + vec_y < n \
                    and visited_matirx[now_x-1 + vec_x][ now_y-1 + vec_y] != 1\
                        and (road_matrix[now_x-1][now_y-1] == [] or [now_x-1 + vec_x, now_y-1 + vec_y] not in road_matrix[now_x-1][now_y-1]):
                            q.append((now_x + vec_x, now_y + vec_y))
                            visited_matirx[now_x-1 + vec_x][now_y-1 + vec_y] = 1
                            #소를 만나면 카운트 증가
                            if cow_matrix[now_x-1 + vec_x][now_y-1 + vec_y] == 1:
                                now_count += 1
        return (cow_number - 1) - now_count

    for now_cow in cow_list:
        count += bfs_cow(now_cow)
        cow_matrix[now_cow[0] - 1][now_cow[1] - 1] = 0
        cow_number -= 1


    print(count)

solution()