sw Yoo

sw Yoo

No sweat, no sweet

In [1]: 
1
2
3
4
5
6
7
8

import sys
import numpy as np
import random, math
import logging, argparse, yaml, copy
import matplotlib.pyplot as plt
sys.path.append('/home/swyoo/algorithm')
from utils.verbose import logging_time, printProgressBar
from copy import deepcopy

1767. 프로세서 연결하기

삼성 SW link

c++ 로 구현된 좋은 코드를 찾아서 이를 바탕으로 python으로 구현하였다.

Notation은 $n \times n$ array 가 주어졌을때,
이 안에 들어있는 processor의 갯수를 $M$ 이라 하자.

각 processor 마다 동,서,남,북,행동X 5가지 cases을 모두 고려해 전선을 까는 경우에 대해 모든 프로세서를 탐색 해보고,
프로세서를 가장 많이 가동 할 수 있으면서 전선이 최소로 필요한 상황에서 최소 전선의 수를 찾는 것이 목표이다.

최악의 경우 모든 cases를 enumerate하는 경우 $O(n5^M)$ 시간이 걸린다.

  • 각 프로세서 마다 최대 5번의 방향성을 고려해야 함.
  • inline, drawline 함수는 $O(n)$ 시간이 걸림.

    가정상황: $n^2 < 5^M$

하지만, 밑의 방식으로 코딩하면 drawline을 통해 주변 프로세서들이 가능한 방향이 pruning되기 때문에
최악의 경우와 같이 모두 조사하는 상황은 거의 발생하지 않는다.

In [2]: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

pnum = 0  # 찾아야할 파워가 연결된 프로세서 갯수
ans = 1e8  # 찾아야할 사용된 전선들의 최소길이
n = 0
a = []

def isline(r, c, dir):
    global a, n
    if dir == 0:
        for j in range(c + 1, n):
            if a[r][j] != 0:
                return False
    elif dir == 1:
        for j in range(c - 1, -1, -1):
            if a[r][j] != 0:
                return False
    elif dir == 2:
        for i in range(r + 1, n):
            if a[i][c] != 0:
                return False
    elif dir == 3:
        for i in range(r - 1, -1, -1):
            if a[i][c] != 0:
                return False
    return True

def drawline(r, c, dir, fill):
    """ fill=2 means draw
        fill=0 means delete. """
    global a, n
    line = 0
    if dir == 0:
        for j in range(c + 1, n):
            a[r][j] = fill
            line += 1
    elif dir == 1:
        for j in range(c - 1, -1, -1):
            a[r][j] = fill
            line += 1
    elif dir == 2:
        for i in range(r + 1, n):
            a[i][c] = fill
            line += 1
    elif dir == 3:
        for i in range(r - 1, -1, -1):
            a[i][c] = fill
            line += 1
    return line

@logging_time
def solve():
    global a
    def dfs(p, pidx, nump, line):
        """
        p 는 프로세서 인덱싱 정보, pidx는 조사할 프로세서 인덱스,
        nump는 power가 연결된 프로세서 최대 수, line은 조사중인 전선 길이
        """
        global a, pnum, ans, n
        if pidx == len(p):  # 모든 프로세서에 대해 조사 끝났을 경우
            if pnum < nump: # 더 많은 프로세서를 가동할 경우를 찾을 경우
                ans = line
                pnum = nump
            elif pnum == nump: # 프로세서는 이전과 일치하지만, 
                if ans > line: # 더 적은 전선이 필요한 상황을 찾을 경우
                    ans = line
            return
        
        for i in range(4):  # 동, 서, 남, 북 에 대해 조사
            if isline(*p[pidx], i):  # 현재 프로세서를 기준으로 i 방향으로 전선을 까는 것이 가능한지 조사
                # 전선을 drawline을 통해 깔고, 현재 line수를 업데이트한 상태로 다음 process에 대해 조사
                dfs(p, pidx + 1, nump + 1, line + drawline(*p[pidx], dir=i, fill=2))
                drawline(*p[pidx], dir=i, fill=0) # roll back
        dfs(p, pidx + 1, nump, line) # no drawing case

    # dfs 시작지점 지정을 위해 연결되지 않은 프로세서 인덱싱(가장자리는 이미 연결됨)
    p = []
    for i in range(1, n - 1):
        for j in range(1, n - 1):
            if a[i][j] == 1:
                p.append((i, j))
    # 가장 자리를 제외하고, 전선을 연결해가며 프로세서 연결이 최대가 될때의 전선 길이 반환
    dfs(p, pidx=0, nump=0, line=0)
In [3]: 
1
2
3
4
5
6
7
8
9
10
11
12
13

if __name__ == "__main__":
    sys.stdin = open('data/processor.txt')
    T = int(sys.stdin.readline())

    for tc in range(1, T+1):
        n = int(sys.stdin.readline())
        a = []
        pnum = 0
        ans = 1e8
        for _ in range(n):
            a.append(list(map(int, sys.stdin.readline().split())))
        solve(verbose=True)
        print("#{} {}".format(tc, ans))

1
2
3
4
5
6
7

WorkingTime[solve]: 0.89335 ms
#1 12
WorkingTime[solve]: 9.07135 ms
#2 10
WorkingTime[solve]: 56.23579 ms
#3 24

Review

복습하고자 다시 풀어보았다. 두 가지 주의 사항이 있었다.

  1. 문제의 조건
    이 문제에서 분명히 확인해야하는 점은 선은 일직선으로만 그을 수 있고,
    중간에 어떠한 프로세서나 줄 같은 방해물이 없어야 그 프로세서가 연결 될 수 있다. (실수로, 프로세서 끼리 연결되거나 줄끼리 겹치는 경우도 연결되도록 해버려서 한참 헤매었다.)
    다음의 함수들이 조건을 만족시키기 위한 핵심 함수들이다. 
    1
2

    def go(i, j, ax0, ax1):
 # TODO ...

    1
2

    def adj(i, j):
 # TODO ...

    1
2

    def marking(i, j, draw, remove=False):
 # TODO ...
  2. pruning
    pruning 하지않으면 시간초과로 통과 할 수 없다. 따라서, 한 프로세서가 power-on 되지 않는 경우에는
    아무 선도 연결 하지 않은 case로 몰아서 처리하면, pruning 된다. 
    1
2
3
4
5

    def dfs(...):
 ...
 for isConnect, draw in adj(*pcs[pidx]):
     if isConnect:  # pruning: it is important.
         ...
In [4]: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

import sys
from sys import stdin
import numpy as np
from utils.verbose import logging_time
sys.setrecursionlimit(10000)

@logging_time
def solution(grid):
    ncore, ans, n = 0, 1e10, len(grid)
    pcs = [(i, j) for i in range(1, n - 1) for j in range(1, n - 1) if grid[i][j]]
    up, down, left, right = (-1, 0), (1, 0), (0, -1), (0, 1)

    def go(i, j, ax0, ax1):
        x, y = i + ax0, j + ax1
        draw = []
        while 0 <= x < n and 0 <= y < n:
            if grid[x][y] != 0: return False, []
            draw.append((x, y))
            x, y = x + ax0, y + ax1
        return True, draw

    def adj(i, j):
        for direction in up, down, left, right:
            yield go(i, j, *direction)

    def marking(i, j, draw, remove=False):
        for x, y in draw:
            grid[x][y] = 2 if not remove else 0

    def dfs(pidx, core, line):
        nonlocal ncore, ans
        if pidx == len(pcs):
            if ncore < core:
                ncore, ans = core, line
            elif ncore == core and ans > line:
                ans = line
            return

        for isConnect, draw in adj(*pcs[pidx]):
            if isConnect:  # pruning: it is important.
                marking(*pcs[pidx], draw=draw)
                dfs(pidx + 1, core + 1, line=line + len(draw))
                marking(*pcs[pidx], draw=draw, remove=True)
        dfs(pidx + 1, core, line=line)  # nothing case.

    dfs(0, core=0, line=0)
    return ans

stdin = open('data/processor.txt')
input = stdin.readline

T = int(input())
for t in range(1, T + 1):
    n = int(input())
    grid = [list(map(int, input().split())) for _ in range(n)]
    ans = solution(grid, verbose=True)
    print('#{} {}'.format(t, ans))

1
2
3
4
5
6
7

WorkingTime[solution]: 0.76890 ms
#1 12
WorkingTime[solution]: 8.89230 ms
#2 10
WorkingTime[solution]: 59.32403 ms
#3 24

Test

In [5]: 
1
2
3
4
5
6
7
8
9
10
11
12

n = 10
grid = np.zeros(shape=(n, n), dtype=int).tolist()
pcs = [(random.randint(0, n - 1), random.randint(0, n - 1)) for _ in range(n)]
for x, y in pcs:
    grid[x][y] = 1
print(np.array(grid))

print(solution(deepcopy(grid), verbose=True))
a = deepcopy(grid)
pnum, ans = 0, 1e8
solve(verbose=True)
ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14

[[0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 1 0 0 0]
 [1 0 0 0 0 1 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 1 0 0 0]
 [0 0 1 0 0 1 0 0 0 0]
 [0 0 0 0 0 1 0 0 0 0]
 [0 1 1 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 1 0 0]]
WorkingTime[solution]: 20.28561 ms
18
WorkingTime[solve]: 19.77015 ms


1

18

Generate Toy Examples.

In [6]: 
1
2

gridstr = '\n'.join(' '.join(str(e) for e in row) for row in np.array(grid).tolist())
print(gridstr)

1
2
3
4
5
6
7
8
9
10
11

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
1 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
In [7]: 
1
2

grid = [list(map(int, rows.split())) for rows in gridstr.split('\n')]
grid

1
2
3
4
5
6
7
8
9
10

[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
 [1, 0, 0, 0, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
 [0, 0, 1, 0, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
 [0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 1, 0, 0]]
In [8]: 
1

print(solution(deepcopy(grid), verbose=True))

1
2
3

WorkingTime[solution]: 20.10751 ms
18

Leave a comment

You may also enjoy

Reeds-Shepp (RS) Path

18 minute read

이동체의 운동 구속조건을 반영하면 전진과 후진 경로에 대한 48가지 경로의 조합을 체크하는 RS path를 배워보자.

Model Predictive Control (MPC)

17 minute read

motion model로 다음 상태를 예측하여 비용함수를 만들고 모델을 제약사항으로 최적화를 하여 제어값을 찾아내는 MPC에 대해서 배워보자

RRT star

15 minute read

RRT star 알고리즘에 대해서 알아보자.