토리로그

너무나도 어렵군... 화이팅... 🔥

문제

소싯적 호석이는 골목 대장의 삶을 살았다. 호석이가 살던 마을은 N 개의 교차로와 M 개의 골목이 있었다. 교차로의 번호는 1번부터 N 번까지로 표현한다. 골목은 서로 다른 두 교차로를 양방향으로 이어주며 임의의 두 교차로를 잇는 골목은 최대 한 개만 존재한다. 분신술을 쓰는 호석이는 모든 골목에 자신의 분신을 두었고, 골목마다 통과하는 사람에게 수금할 것이다. 수금하는 요금은 골목마다 다를 수 있다.

당신은 A 번 교차로에서 B 번 교차로까지 C 원을 가지고 가려고 한다. 호석이의 횡포를 보며 짜증은 나지만, 분신술을 이겨낼 방법이 없어서 돈을 내고 가려고 한다. 하지만 이왕 지나갈 거면, 최소한의 수치심을 받고 싶다. 당신이 받는 수치심은 경로 상에서 가장 많이 낸 돈에 비례하기 때문에, 결국 갈 수 있는 다양한 방법들 중에서 최소한의 수치심을 받으려고 한다. 즉, 한 골목에서 내야 하는 최대 요금을 최소화하는 것이다.

 

예를 들어, 위의 그림과 같이 5개의 교차로와 5개의 골목이 있으며, 당신이 1번 교차로에서 3번 교차로로 가고 싶은 상황이라고 하자. 만약 10원을 들고 출발한다면 2가지 경로로 갈 수 있다. 1번 -> 2번 -> 3번 교차로로 이동하게 되면 총 10원이 필요하고 이 과정에서 최대 수금액을 5원이었고, 1번 -> 4번 -> 5번 -> 3번 교차로로 이동하게 되면 총 8원이 필요하며 최대 수금액은 6원이 된다. 최소한의 수치심을 얻는 경로는 최대 수금액이 5인 경로이다. 하지만 만약 8원밖에 없다면, 전자의 경로는 갈 수 없기 때문에 최대 수금액이 6원인 경로로 가야 하는 것이 최선이다.

당신은 앞선 예제를 통해서, 수치심을 줄이고 싶을 수록 같거나 더 많은 돈이 필요하고, 수치심을 더 받는 것을 감수하면 같거나 더 적은 돈이 필요하게 된다는 것을 알게 되었다. 마을의 지도와 골목마다 존재하는 호석이가 수금하는 금액을 안다면, 당신이 한 골목에서 내야하는 최대 요금의 최솟값을 계산하자. 만약 지금 가진 돈으로는 절대로 목표 지점을 갈 수 없다면 -1 을 출력하라.

20168과 20182, 20183번은 문제가 같다. 다른점은 주어진 변수의 입력 범위이다.

20168번은 N의수가 최대 10까지이다. 따라서 모든 교차로를 확인할 경우 최대 O(n^2)의 복잡도를 가지는데 이는 100이므로 시간초과 범위 내에서 해결이 가능하다.

반면 20182번은 N의 수가 최대 100,000까지여서 O(n^2)의 경우 100,000,000,000 이 되므로 5초 제한에서 timeout이 발생한다. 따라서 20182번과 20183번은 탐색의 수를 줄여야 한다.

20168 : DFS 로 풀기

앞선 문제는 연산횟수가 최대 100이므로 DFS로 풀어보았다.

import sys
input = sys.stdin.readline
n, m, a, b, c = map(int, input().split())
road = [[] for _ in range(n+1)] # index가 교차로 (n+1), 이어지는골목과 비용을 append 한다
for _ in range(m):
    from_c, to_c, cost = map(int, input().split())
    # 양방향 골목이므로 두번 삽입
    road[from_c].append((to_c, cost))
    road[to_c].append((from_c, cost))

res_max_min = sys.maxsize
def dfs(from_city, total_cost, max_cost):
    global res_max_min
    # 경로의 총 비용이 소지한 비용을 넘어서면 return
    if total_cost > c:
        return
    # 위의 validation을 통과하고, 도착지점에 도착하면 값 갱신
    if from_city == b:
        res_max_min = min(res_max_min, max_cost)
        return
    # 비용미초과, 도착지점 미도달 상태라면 계속해서 탐색
    for to_city, to_cost in road[from_city]):
    	# 이전에 방문하지 않은 교차로만 탐색
        if not visit[to_city]:
            visit[from_city] = True
            dfs(to_city, total_cost+to_cost, max(max_cost, to_cost))
            visit[from_city] = False
visit = [False] * (n+1)
visit[0] = True
visit[a] = True
dfs(a, 0, 0)
if res_max_min == sys.maxsize:
    res_max_min = -1
print(res_max_min)

해당 풀이로 20168번 풀이가 가능하다.

20182, 20183 : 이분탐색과 다익스트라 알고리즘 활용하기

정답에서 요구하는 것은 "최소값이 정답이 되는 것" 이다. 이러한 유형의 문제에서는 "이분탐색" 으로 정답이 되는 값을 탐색하며 풀 수 있다. 참고로 이분탐색법은 값이 정렬되어 있을때 O(logN)의 시간복잡도를 지닌다.

이분탐색법으로 정답이 되는값 "목표 교차로까지 가는 경로중 최대 비용들 중에서의 최소값" 을 탐색하며, 해당 값으로 도착지점까지 도달할 수 있는지 다익스트라 알고리즘으로 탐색한다.

모든 골목의 비용 리스트 = costs
이분탐색으로 탐색한 값 = mid
이분탐색으로 탐색한 값 기준 제한 골목 비용 = costs[mid]
한개 경로의 최대값 one_max
모든 경로의 one_max 들 중에서의 최소값 = road_max_min
교차로 = 노드
골목 = 간선

다익스트라 알고리즘은 a에서 b까지 가는 경로의 최단거리를 찾아낸다. 즉 시작지점에서 도착지점까지 최소비용을 찾아내고, 그 값이 costs[mid] 값과 같거나 그 값보다 적다면 해당 그 값이 답이 될수 있다는 뜻이다.

반면, 최단거리 탐색 중 한개 간선의 비용이 mid값 보다 크다면 해당 조건으로 탐색은 불가능한 것이므로 mid 값을 키워주며 탐색한다.

import heapq
import sys
sys.stdin = open("input.txt")
n, m, a, b, c = map(int, input().split())

costs = []
road = [[] for _ in range(n + 2)]
for _ in range(m):
    from_cc, to_cc, ccost = map(int, input().split())
    costs.append(ccost)
    road[from_cc].append((to_cc, ccost))
    road[to_cc].append((from_cc, ccost))

def check_cost(mid):
    distances = [sys.maxsize for _ in range(n + 1)]
    distances[a] = 0
    edge = []
    heapq.heappush(edge, [0, a])  # 비용과 현재 노드
    while edge:
        this_cost, this_node = heapq.heappop(edge)
        # 최단경로 확인한다 : 이미 이번 노드로 가는 비용이 누적 비용보다 적다면 갱신 X
        if distances[this_node] < this_cost:
            continue
        for next_node, next_cost in road[this_node]:
            if distances[next_node] > this_cost + next_cost and next_cost <= mid:
                distances[next_node] = next_cost + this_cost
                heapq.heappush(edge, [this_cost + next_cost, next_node])
    if distances[b] > c:
        return False
    return True
road_max_min = sys.maxsize
costs.sort()
lt = 0
rt = len(costs) -1
while lt <= rt:
    mid = (lt + rt) // 2
    # mid 값을 최대로 갖는 경로가 있는지 확인한다.
    check_res = check_cost(costs[mid])
    if check_res:
        # 있다면 최대 값을 더 줄여본다
        rt = mid -1
        # 답으로 기록한다.
        road_max_min = min(road_max_min, costs[mid])
    else:
        # 없다면 최대값을 더 늘려본다
        lt = mid +1
if road_max_min == sys.maxsize:
    print(-1)
else:
    print(road_max_min)

이때 check_cost 함수 내에서 목표골목 b까지의 최단거리가 완성되었을때 그 값이 c 보다 크다면 결국엔 갈수 없는 경로이므로 mid 값을 줄여준다.

위 풀이로 20182과 20183 모두 해결 가능하다.

Python으로 풀었을 경우 백준에서는 Python3 와 Pypy3 두가지로 채점 가능하다.

Python3로 채점했을때 시간초과가 뜬 경우 Pypy3로 채점하면 통과하기도 하는데 위 문제중 20182가 그러한 경우이다. 따라서 Pypy3 로 제출하면 된다!

회사에서는 유저 행동에 대한 후처리 요청을 하는데 AWS의 SQS를 사용한다.

이미 입사했을때 SQS 설계가 다 되어있는 상태여서 초기 세팅은 알지 못했지만, 얼마 전 어떤 기능에서 메세지 전달관련하여 에러가 발생하는거 같아 조금 살펴보게 되었다.

결론적으론 SQS문제는 아니었고, 메세지를 전달받아 실행된 Lambda 프로젝트에서 KeyError 가 발생하여 병렬처리되는 Lambda가 불규칙적으로 중단되는 오류였다.

처음에 메세지 관련 문제일 것이라고 생각했던 이유가

1. 메세지 한개 전달 시 처리가 정상적으로 완료된다.

2. 메세지 두개 전달 시 처리가 정상적으로 완료된다.

3. 1과 2의 메세지 총 3개를 전달시 3개중 2개만 처리되고 하나는 처리중에서 무한대기 상태에 빠진다. (Lambda에서 Exception이 발생하여 남아있는 메세지를 미쳐 처리하지 못하게 된 상태)

위와 같은 문제가 발생하여 3개이상의 메세지 전달과정에서 오류가 있지 않았나 생각했었다. (결론은 아녔다..!!)

1. AWS의 메세징

AWS에서 제공하는 메세징 기능에는 SQS와 SNS가 있다. 흔히 Producer 로부터 메세지가 생성되어 메세징 서비스가 메세지를 전달받으면 이 내용을 Consumer에게 전달하여 작업이 처리되도록 한다. 이후 Consumer가 메세지를 생성하게 되면 메세징 서비스를 통해 Producer에게 다시 전달되기도 한다.

즉, 메세징 서비스는 요청한 곳과 요청을 받아 처리하는 곳의 전달자를 수행한다.

1) SQS (Simple Queue Service)

SQS는 Queue 기반 메세징 서비스로 선입선출 (FIFO) 로 메세지가 처리된다. 따라서 동시다발적으로 요청이 들어와도 요청 순서에 따라 순차적인 메세지 처리가 가능하다.

이러한 SQS는 한개의 Consumer에게만 메세지 전달이 가능하다.

만약 유저의 행동이 "구매" 와 "판매" 두가지 기능이 있다고 했을때, 이벤트 발생시 Lambda와 같은 프로젝트로 작업 처리 요청을 보내기 위해선 구매관련 SQS, 판매관련 SQS를 생성해야 한다.

이렇게 되면 구매와 판매 각각의 기능에 서로 병렬적으로 작업의 순차처리가 가능해진다.

ex)

구매1 -> 구매2 -> 판매1 -> 구매3 -> 판매2

위와 같은 유저 요청이 순차적으로 발생했다고 했을때 SQS가 한개에서 처리되었다면 요청들어온 순서대로 작업이 처리될 것이다.

하지만 구매와 판매의 SQS가 분리되어있기 때문에

구매 Queue : 구매1 -> 구매2 -> 구매3

판매 Queue : 판매1 -> 판매2

위와 같이 작업이 처리된다.

2) SNS (Simple Notification Service)

SNS역시 Consumer (구독자 라고 부르기도 한다) 에세 메세지를 전달하는 역활을 수행한다. 이때 Consumer는 Lambda와 같은 기능 뿐만이 아니라 SQS가 될수도 있고, 모바일이나 웹 자체에 알람을 보낼수도 있다.

SQS와 달리 SNS는 복수개의 Consumer를 가질 수 있다. 메세지 내용에 따라 서로 다른 Consumer에게로 메세지 전달이 가능하기 때문이다.

만약 위의 SQS예제에서 SNS를 사용하였다면 구매와 판매 각각의 메세징 서비스를 사용하지 않고, 발생하는 메세지는 모두 SNS로 보낸 다음 SNS에서 각각의 SQS로 메세지를 전달하여 최종적으로 요청이 처리되도록 구조를 설계할 수 있다.

이렇게 되면 SNS비용과 SQS비용이 모두 발생하기 때문에 한개의 SNS로 각 서비스에 요청을 처리하도록 하기도 한다.

2. 메세징 사용 이유

메세징 서비스는 기본적으로 비동기로 돌아간다. 때문에 작업 요청이 들어오고, 이 요청을 마무리 하기까지 시간이 오래걸리는 경우 작업 요청자는 결과가 나올때까지 기다려야 하는 과정이 없게 된다. (요청을 던지는 것이니까)

특정 조건에 대한 다량의 데이터를 조회하거나, 외부 api 를 호출하여 데이터를 가공하는 등과 같이 작업처리에 시간이 오래걸린다면 이러한 메세징 기반 서비스를 도입해 요청에 따른 처리를 비동기로 수행하게 하는것이 좋을 듯 하다.

물론 비동기로 처리하였을때 그 결과를 다시 확인하는건 필수..!!

(메시지 처리 결과를 요청을 처리한 곳에서 저장하도록 하고, 그 결과를 유저가 확인할 수 있다던가...)

+) 메세지 3개중 일부만 성공한 이유.. (파악중)

SQS, SNS와는 무관하지만 애초에 이 기능을 살펴보게 만든 이슈가 아직 의문이다.

해당 프로젝트는 Lambda로 구성되어있고, SQS로부터 전달받은 메세지는 특정 키 안에 list 형태로 되어있다. 어떤 요청을 처리하든지 공통 처리 부분에서 무조건 Key Error가 발생하게 되는데, 그렇다면 처음 요청에서 바로 에러가 발생해야 하는게 아닌가? 하는 생각을 하였다.

디버깅을 하면서 그 흐름을 따라가보니 정말로 첫번째 요청때도 KeyError가 발생하지만 이때에는 Exception이 일어나지 않고, 두번째 요청에서 또한번의 KeyError가 발생했을때 Exception이 발생한다.

코테연습을 하면서 '플로이드-워셜' 알고리즘을 활용한 문제를 마주했다.

처음에는 '플로이드-워셜' 알고리즘이 무엇인지 몰랐던 상태라 해당 알고리즘을 먼저 공부했고, 이를 문제에 활용했는데

개념은 알겠으나 왜 이렇게 적용하는지 이해가 되지 않은 부분이 있었다.

문제는 백준의 11403번 문제로 확인했다.

"""
3
0 1 0
0 0 1
1 0 0
"""
n = 3
city = [[0, 1, 0], [0, 0, 1], [1, 0, 0]]

1. 처음 풀이 : 오답

처음엔 "세개 노드를 확인하면서 첫번째와 세번째의 노드가 모두 두번째 노드와 연결되어있으면 첫번째와 세번째 노드도 연결 된것" 이라는 개념으로 아래와 같이 풀었었다.

def solution_my():
    """
    i에서 j의 경로를 탐색하면서 거쳐가는 k 노드의 값을 확인, k 값으로 연결된 i, j는 연결가능하다
    """
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if city[i][k] == 1 and city[k][j] == 1:
                    city[i][j] = 1
    
""" 연결 체크 이후 답
0 1 1
1 1 1
1 1 1
"""

하지만 0에서 0으로 가는 경로가 체크되지 않았다. 0 -> 1 / 1 -> 2 / 2 -> 0 경로가 존재하기 때문에 0 -> 0 의 경로도 체크되야 한다.

위와같은 오류가 발생한 까닭은

0에서 연속적으로 연결된 노드 정보를 미쳐 파악하기 전에 노드 0의 연결정보 파악이 끝났기 때문이다.

i = 0 / j = 2 / k = 1 일때 i와 j의 연결정보를 갱신한다 citi[0] = [0 1 0] -> [0 1 1]

이후 i는 1로 갱신되어 0번째 노드의 탐색이 종료된다.

위 과정을 2번 반복하면 이전에 체크되지 않은 노드가 체크되어 정답이 된다.

for _ in range(2):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if city[i][k] == 1 and city[k][j] == 1:
                    city[i][j] = 1
"""
1 1 1
1 1 1
1 1 1
"""

하지만 2번확인해도 누락이 생긴다면? 이 방법으로는 오류를 근본적으로 해결할 수 없다.

다시 플로이드-워셜의 풀이로 왜 성공했는지 확인해보자.

2. 플로이드-워셜 풀이

def solution_floid():
    """
    i에서 j의 경로를 탐색하면서 거쳐가는 k 노드의 값을 확인, k 값으로 연결된 i, j는 연결가능하다
    """
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if city[i][k] == 1 and city[k][j] == 1:
                    city[i][j] = 1
""" 탐색 후 city 값
1 1 1
1 1 1
1 1 1
"""

내 풀이와 달리 모든 노드탐색이 확인되어 한번에 정답이 나왔다. (0에서 0으로 가는 경로도 체크되었다)

내 풀이와 위 풀이가 다른점은 탐색 노드 (k) 를 첫번째 for loop값으로 했다는 것이다.

즉, 시작노드가 i이고 종료노드가 j 일때 그 사이에 k 노드가 있는지 확인했던 내 풀이와 달리

탐색 노드 k를 기준으로 시작노드가 i일때 종료노드가 j이게 되는 수를 파악한 것이다.

플로이드-워셜 풀이를 기준으로 하면 가장 먼저 확인되는 추가 경로는 [2,1] 이다 해당 경로는 k 값이 0일때 2->0 이고, 0->1인게 확인되어 추가된다.

그 다음으로 추가되는 경로는 [0,2]이며 k값 1을 통해 경로가 확인된다. 위 방법의 풀이는 시작노드 값을 반복해서 확인하므로 내 풀이에서 0번 노드의 탐색을 바로 종료한것과 달리 k값을 탐색할때마다 확인하게 된다.

i값이 0이고, j값도 0일때 k 값에 따른 탐색 결과를 확인해 보면 다음과 같다.

#1 i=0, j=0, k=0 -> No
#2 i=0, j=0, k=1 -> No
"""
이때 i가 0이고, j가 2인 상황에서 k가 1일때 연결정보가 확인되므로
city[0][2] 값이 1로 갱신된다.
"""
#3 i=0, j=0, k=2 -> Yes
"""
위 과정으로 city[0][2]가 기존에 연결되지 않은 정보에서 갱신되었고,
city[2][0]은 원래 연결정보가 존재했으므로
city[0][0]에 대한 연결정보가 갱신된다.
"""

직접 풀이를 써내려가며 확인해 보니 왜 탐색노드를 첫번째 for loop 로 두었는지 감은 오지만, 아직까지 남에게 설명할 정도로의 감은 익히지 못한듯 하다. 추가로 플로이드-워셜 문제를 계속해서 풀면서 감을 익혀야 겠다.

!! 가중치가 주어진 상황 문제 풀어보기 !!

여러가지 조건에서 최단거리를 구하는 알고리즘 문제가 나오기 때문에 관련 공부는 필수인 듯 하다.

기존에는 다익스트라 알고리즘만 활용가능한 수준이었는데 이번에 11403번 문제를 보면서 플로이드 워셜 알고리즘을 처음 사용해 보았다.

처음 풀이에서는 플로이드 워셜 알고리즘을 사용하지 않고, deque를 활용하여 문제를 풀었는데 백준 문제 기준으로 deque를 사용한 풀이의 시간이 덜 소요되는것으로 보였다.

두가지 풀이에서 어떤 점이 소요시간의 차이를 일으켰는지 알아보고자 한다.

1. deque 활용

deque를 활용한 풀이는 다음과 같다.

import sys
import time

sys.stdin = open("input.txt")
from collections import deque
n = int(input())
city = [list(map(int, input().split())) for _ in range(n)]

# deque 버전
def solution_deque():
    visit = [[0]*n for _ in range(n)]
    dq = deque()
    for from_first, m in enumerate(city):
        for to_city, moving in enumerate(m):
            if moving == 1 and visit[from_first][to_city] == 0:
                visit[from_first][to_city] = 1
                dq.append(to_city)
                while dq:
                    to_city = dq.popleft()
                    for next_to, next_move in enumerate(city[to_city]):
                        if next_move == 1 and visit[from_first][next_to] == 0:
                            visit[from_first][next_to] = 1
                            dq.append(next_to)

    for i in visit:
        print(*i)

여기서 visit은 방문여부를 체크하기도 하지만, 최종 답을 적기 위해 그 초기값을 0으로 하였다.

city 이중배역에 문제로 주어진 간선 정보를 담았다.

이후 첫번째 for loop 에서 현재 확인하고자 하는 노드를 "from_fist" 값으로 하고, from_first와 연결된 노드를 "to_city" 라고 하였다.

from_first 에서 to_city 로 가는 간선이 존재한다면 visit정보를 1로 업데이트 하고, 간선 정보를 deque에 담는다.

이후 deque값이 존재할 동안 (while 조건) 이어지는 간선 정보를 확인한다.

to_city 를 기준으로 for loop로 찾는 도시 "next_to" 의 1인 경우 (next_move가 1) 방문여부를 확인하고 from_first에서 next_to가 연결되었음을 체크한다.

또한, to_city 에서 next_to의 연결정보를 다시 deque에 담아 next_to의 도시에서 시작하는 연결정보를 계속해서 탐색한다.

from collections import deque
# from_first = 0
# to_city = 1
city = [[0, 1, 0], [0, 0, 1], [1, 0, 0]]
"""
from_first에서 to_city의 연결정보가 1이므로 방문여부 확인 후 체크한다.
그리고 이어서 탐색하기 위해 해당 연결 정보를 deque에 담는다
"""
dq = deque()
if city[from_first][to_city] == 1 and visit[from_first][to_city] == 0:
	visit[from_first][to_city] = 1
    dq.append(to_city)
    # dq에 담긴 정보에서 이어서 탐색 한다. (from_first에서 시작한 연결정보가 끝날때까지)
    while dq:
    	from_city, to_city = dq.popleft()
        for next_to, next_move in enumerate(city[to_city]):
        	if next_move == 1 and visit[first_from][next_to] == 0:
            	visit[first_from][next_to] = 1
                """
                to_city에서 next_to가 연결되어있다면 from_first에서 next_to도 연결된 것이다.
                방문여부를 체크하고, 이어서 연결정보를 탐색하게 한다.
                """
                dq.append(next_to)

한가지 상황을 예로 들어 과정을 풀이하면 위와 같다. 총 시간복잡도는 N^3으로 확인된다. 단, 자기자신의 노드로 가는 경우는 0이기 때문에 해당 경우의 수는 확인하지 않는다.

2. 플로이드-워셜 활용

플로이드-워셜 알고리즘이란 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다.

위 알고리즘을 더욱 잘 활용할수 있는 예제는 "가중치가 있는 간선" 이 주어졌을때 인데, 위 문제의 경우 가중치가 없어 오로지 "연결 가능한 노드인지" 를 확인만 하면 된다.

플로이드-워셜 알고리즘으로 i 에서 j 노드로 갈때 k 노드를 거쳐서 갈수있는지 확인하여 i 에서 j 노드의 연결을 확인한다. i에서 j 노드의 모든 수를 확인하는 N^2 시간복잡도에서 k 노드 확인 경우를 추가하여 최종적으로 N^3의 시간복잡도를 보이고, 모든 노드를 확인하여 제외되는 경우는 없다.

def solution_floid():
    """
    i에서 j의 경로를 탐색하면서 거쳐가는 k 노드의 값을 확인, k 값으로 연결된 i, j는 연결가능하다
    """
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if city[i][k] == 1 and city[k][j] == 1:
                    city[i][j] = 1
    for row in city:
        print(*row)

3. 두 풀이의 풀이시간 차이

2) 동일한 노드수에서 간선 비율의 차이에 따른 시간차이

i. 노드의 수가 14개

당연히 알고리즘으로 풀면 더 빠르겠지! 싶었던 생각이 예제로 소요시간을 확인하며 깨졌다.

노드의 수가 14개이면서, 간선의 비율이 약 25%, 약 52% 약 92% 일때 시간을 측정해 보았다.

# 노드의 수 14 / 간선비율 약 25%
# deque 소요시간 : 0.0006220340728759766
# floyd 소요시간 : 0.0008339881896972656

14
0 0 0 1 0 0 0 1 0 0 0 1 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0
1 0 0 0 0 0 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 1 0 0 0 0 0 1 0 0 0 1 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0
1 0 1 0 1 0 1 0 1 0 1 0 0 0
0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 0 0 0 1 0 0 0

# 간선 비율 약 52%
# deque 소요시간 : 0.0006856918334960938
# floyd 소요시간 : 0.0009648799896240234

14
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0

# 간선비율 약 92%
# deque 소요시간 : 0.0006418228149414062
# floyd 소요시간 : 0.0008568763732910156

14
0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0

노드수가 14개일 경우 간선의 비율차로는 플로이드-워셜의 소요시간이 항상 더 길게 나온다.

ii) 노드 수가 5개

# 간선비율 약 80%
# deque 소요시간 : 9.012222290039062e-05
# floyd 소요시간 : 8.797645568847656e-05

5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

# 간선비율 약 20%
# deque 소요시간 : 9.918212890625e-05
# floyd 소요시간 : 9.894371032714844e-05

5
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0

노드의 수가 5개이거나, 이의 약 3배인 14개이거나 플로이드-워셜 풀이로 풀었을 경우 소요시간이 더 크게 나오는것을 확인 할 수 있다.

극단적으로 노드의 수가 3개일 경우에는 플로이드-워셜의 소요시간이 더 적게 나오긴 하다

# 간선비율 : 약 33%
# deque 소요시간 : 3.910064697265625e-05
# floyd 소요시간 : 2.9087066650390625e-05

3
0 1 0
0 0 1
1 0 0

하지만 보통의 문제에서는 n의 범위가 3까지일리가 없으니... 시간복잡도를 생각한다면 플로이드-워셜이 아닌 deque를 사용한 풀이를 선택해도 될것같다.

문제

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

분할정복 알고리즘 ?
기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트나  병합정렬이 있다.
출처 : 나무위키 - 분할 정복 알고리즘

사실 처음엔 큰 문제를 작게 쪼개서 계산?? 이 문제에 적용이 된다고? 싶었지만 처음 접해보는 분할정복 문제였어서 감이 안왔던듯 하다.

직접 문제를 손으로 써내려가면서 이해해 보았다.

문제에서 주어진 조건은 크게 두가지가 있다.

1. 주어진 영역 내 서로 다른 색이 존재 할 경우 해당 영역을 4분할 한다.

2. 정사각형 내 동일 색상 단위로 총 몇개 정사각형이 존재하는지 출력한다.

따라서 1번 조건에 맞을 경우 문제를 쪼개면 되는것이고, 쪼갠 상황에서 2번 조건에 맞는다면 답으로 기록하면 된다.

시작점은 [0, 0] 으로 한다. 시작점의 색상을 기억해 두고, 일정한 인접 행렬을 탐색하다가 다른 값이 나온다면 1번 조건에 부합하므로 즉시 4분할을 해준다.

분할된 영역의 구간은 규칙적으로 변경된다.

python의 // 는 값을 나눈 몫을 반환하므로 n값이 8일때 n//2를 하면 그 값은 4가 된다. 또한 python의 for loop에서 range의 end parameter는 해당 값 "미만"으로 동작하기 때문에 n//2 값을 넣어주면 된다.

처음에 탐색의 시작을 [0,0] 에서 한다고 하였으므로 첫번째 이중 for loop의 탐색 범위는 탐색x는 (이하 xx) x ~ x+n(미만) 이고, 탐색y는 (이하 yy) y ~ y+n 이 된다.

첫번째 cut 에서 또다시 서로다른 색이 발견되어 4분할을 진행해 줄때, x값과 y값의 범위 변화는 규칙적으로 변경된다.

위 규칙을 토대로 풀이를 작성하면 아래와 같다.

import sys
sys.stdin = open("input.txt")
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]

white = 0
blue = 0
def cut(x, y, n):
    global white
    global blue
    check_color = board[x][y]
    for xx in range(x, x+n):
        for yy in range(y, y+n):
            if board[xx][yy] != check_color: # 조건 1 부합 : 4분할 진행
                cut(x=x, y=y, n=n//2) # 1영역 : x = x ~ x+(n//2) | y = y ~ y+(n//2) | n = n//2
                cut(x=x, y=y+n//2, n=n//2) # 2영역 : x = x ~ x+(n//2) | y = y+n//2 ~ y+n//2+n | n = n//2
                cut(x=x+n//2, y=y, n=n//2) # 3영역 : x = x+n//2 ~ x+n//2+n | y = y ~ y+(n//2) | n = n//2
                cut(x=x+n//2, y=y+n//2, n=n//2) # 4영역 : x = x+n//2 ~ x+n//2+n | y = y+n//2 ~ y+n//2+n | n = n//2
                return # 분할은 분할대로 호출해놓고, 값에 적용되는걸 막기 위해 분할 뒤 return 한다.
    # 조건 2 부합 : 분할되지 않으면 모두 색이 같다는 것으로 정답으로 기록한다.
    if check_color == 1:
        blue += 1
    else:
        white += 1

cut(0, 0, n)  # 시작 조건 [0,0]
print(f"{white}\n{blue}")

큰 문제를 쪼갠다는 것과, 4분할 처리 하는 것에 대해 알 수 있었다.!