문제 링크

14466 - 소가 길을 건너간 이유 6

문제 설명

N*N 크기의 격자로 이루어진 농장이 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다.

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

문제 풀이

시도 1 - BFS

1. 가능한 두 소의 combination을 구한다.
2. BFS를 이용해서 출발소-도착소까지 길을 건너지 않고 건널 수 있는 경로를 찾는다.

import sys
from collections import defaultdict, deque
import copy

input = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

N, K, R = map(int, input().split())
roads = defaultdict()
cows = []
board = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(R):
    r1, c1, r2, c2 = map(int, input().split())
    roads[(r1-1, c1-1, r2-1, c2-1)] = 1

for _ in range(K):
    r, c = map(int, input().split())
    cows.append((r-1, c-1))
    board[r-1][c-1] = 1

def in_bound(x, y):
    if x in range(N) and y in range(N):
        return True
    return False

def bfs(cow):
    queue = deque()
    count = 0
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[cow[0]][cow[1]] = True
    queue.append([cow[0], cow[1], visited])

    while queue:
        x, y, visited = queue.popleft()
        visited[x][y] = True
        c_visited = copy.deepcopy(visited)

        if board[x][y] == 1 and (x,y) != cow:
            count += 1
        else:
            for i in range(4):
                nx, ny = x+dx[i], y+dy[i]
                if in_bound(nx, ny) and c_visited[nx][ny] == False:
                    if (x,y,nx,ny) not in roads.keys() and (nx,ny,x,y) not in roads.keys():
                        queue.append([nx, ny, c_visited])
    return count                
    
answer = 0
for cow in cows:
    # c1 -> c2까지 길 안지나고 가는 경로 찾기
    answer += len(cows)- bfs(cow)
    
print(answer//2)

시간초과가 났다 계속,,,,,,,

시도 2

로직을 바꿔서 한 소가 길을 건너지 않고 만날 수 있는 소의 개수를 찾는다.

import sys
from collections import defaultdict, deque
import copy

input = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

N, K, R = map(int, input().split())
roads = [[[] for _ in range(N)] for _ in range(N)]
cows = [[0 for _ in range(N)] for _ in range(N)]
cow_list = []
for _ in range(R):
    r1, c1, r2, c2 = map(int, input().split())
    roads[r1-1][c1-1].append([r2-1, c2-1])
    roads[r2-1][c2-1].append([r1-1, c1-1])

for _ in range(K):
    r, c = map(int, input().split())
    cows[r-1][c-1] = 1
    cow_list.append((r-1, c-1))
num_cows = len(cow_list)

def in_bound(x, y):
    if x in range(N) and y in range(N):
        return True
    return False

def bfs(cow):
    # cow가 길을 건너지 않고 만날 수 있는 소의 개수
    queue = deque()
    count = 0
    visited = [[0 for _ in range(N)] for _ in range(N)]
    visited[cow[0]][cow[1]] = True
    queue.append([cow[0], cow[1]])

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if in_bound(nx, ny) and visited[nx][ny] == 0:
                if roads[x][y] == [] or [nx,ny] not in roads[x][y]:
                    queue.append([nx, ny])
                    visited[nx][ny] = 1
                    if cows[nx][ny] == 1:
                        count += 1
    # 전체 소 - 현재 소 - 길안건너고 만날 수 있는 소 = 길 건너야만 만나는 소
    return num_cows - 1 - count          
    
answer = 0
for cow in cow_list:
    answer += bfs(cow)
    cows[cow[0]][cow[1]] = 0
    num_cows -= 1
    
print(answer)

소요시간

1시간

쉽지않음,,