[BOJ] 14466

me

import sys
from collections import defaultdict
from itertools import combinations
input = sys.stdin.readline

n,k,r = map(int,input().split())
routes=[]
for _ in range(n):
    route=[]
    for _ in range(n):
        route.append([])
    routes.append(route)
for _ in range(r):
    x1,y1,x2,y2 = map(int,input().split())
    routes[x1-1][y1-1].append([x2-1,y2-1])
    routes[x2-1][y2-1].append([x1-1,y1-1])

cows=[]
for _ in range(k):
    x,y = map(int,input().split())
    cows.append([x-1,y-1])

dx=[0,0,-1,+1]
dy=[-1,+1,0,0]
def dfs(start,dest):
    stack = [start]
    visit = [[False]*n for _ in range(n)]
    visit[start[0]][start[1]]=True
    while stack:
        x,y = stack.pop()
        if [x,y] == dest:
            return True
        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]
            if not(-1<nx<n and -1<ny<n): continue # 경계선 밖
            if [nx,ny] in routes[x][y]: continue # 길로 이동이 필요한 곳
            if visit[nx][ny]: continue # 이미 방문한 곳
            visit[nx][ny]=True
            stack.append([nx,ny])
    return False
answer=0
for start,dest in combinations(cows,2):
    if not dfs(start,dest): answer+=1
print(answer)

• 문제를 이해하는데 시간이 걸렸다. 간단히 요약하면 전체 소의 쌍에서 길을 건너지 않고도 만날 수 있는 소의 쌍을 제외하면 된다.
• 1:1 관계로 도달하면 제외하도록 하니 시간 초과가 났다.
• 아무래도 combinations을 쓰면서 나는 것 같고
• 조합으로 하니 전에 방문했던 곳을 한번 더 방문하여 쓸모 없는 시간까지 소비되었다.
• 하지만 조합 말고는 중복되는 쌍을 어떻게 제거해야할지 생각이 안났다.

solution

import sys
from collections import deque
from itertools import combinations
input = sys.stdin.readline

n,k,r = map(int,input().split())
routes = [[[] for _ in range(n)] for _ in range(n)]
for _ in range(r):
    x1,y1,x2,y2 = map(int,input().split())
    routes[x1-1][y1-1].append([x2-1,y2-1])
    routes[x2-1][y2-1].append([x1-1,y1-1])

cows=[]
cow_map=[[False]*n for _ in range(n)]
for _ in range(k):
    x,y = map(int,input().split())
    cows.append([x-1,y-1])
    cow_map[x-1][y-1]=True

dx=[0,0,-1,+1]
dy=[-1,+1,0,0]
def bfs(start):
    global cow_map
    count=0 # 길을 건너지 않고 만날 수 있는 수
    q = deque([start])
    visit = [[False]*n for _ in range(n)]
    visit[start[0]][start[1]]=True
    while q:
        x,y = q.popleft()
        for d in range(4):
            nx=x+dx[d]
            ny=y+dy[d]
            if not(-1<nx<n and -1<ny<n): continue # 경계선 밖
            if [nx,ny] in routes[x][y]: continue # 길로 이동이 필요한 곳
            if visit[nx][ny]: continue # 이미 방문한 곳
            visit[nx][ny]=True
            q.append([nx,ny])
            if cow_map[nx][ny]: # 소라면
                count += 1
    return count
answer= 0
for start in cows:
    if cow_map[start[0]][start[1]]:
        k-=1
        cow_map[start[0]][start[1]]=False
        count = bfs(start)
        answer+= k-count
print(answer)

• 그냥 소 하나씩 해보면서 이 친구가 길을 건너지 않고 만날 수 있는 친구들을 세주면 된다.
• 한 소가 끝나면 그 소는 이미 쌍에 포함이 된 것으로 이 소가 포함된 쌍을 제외하고 찾으면 되니 이 친구만 소 리스트에서 빼주면 된다. 이 방법을 map으로 한 것이다.
• 쌍이니깐 제외해주기..! 이게 조금 이해하기 어려웠다.