[SWEA] 1767 프로세서 연결하기 python

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf&categoryId=AV4suNtaXFEDFAUf&categoryType=CODE&problemTitle=SW&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=3

SW Expert Academy

import sys
sys.stdin = open('./sample_input_1.txt', 'r')

for tc in range(1, int(input()) + 1):
    N = int(input())
    matrix = []
    visited = [[-1] * N for _ in range(N)] # core:0 visit:1, not_visit:-1
    core = []
    for i in range(N):
        tmp = list(map(int, input().split()))
        matrix.append(tmp)
        for j in range(N):
            if tmp[j]:
                core.append((i, j))
                visited[i][j] = 0

    linked_core = 0
    linked_line = 0
    electric_line = [list() for i in range(len(core))]
    # 1 모든 core에서 최소 거리 확인
    for index in range(len(core)):
        tmp = []
        tmp.append(core[index][0])                  # 상
        tmp.append((len(matrix) - core[index][0]) - 1)    # 하
        tmp.append(core[index][1])                  # 좌
        tmp.append((len(matrix) - core[index][1]) - 1)    # 우
        electric_line[index] = tmp

    def backtrack(visit, index=0, total_line=0, total_core=0):
        if index == len(core):
            global linked_line, linked_core
            if linked_core < total_core:
                linked_core = total_core
                linked_line = total_line
                # print(total_core, total_line)
                # print(*visit, sep='\n', end='\n\n')

            elif linked_core == total_core:
                if linked_line > total_line:
                    linked_line = total_line
                    # print(total_core, total_line)
                    # print(*visit, sep='\n', end='\n\n')

        else:# 방향 0,1,2,3, : 상하좌우
            cnt = 0
            if core[index][0] == 0 or core[index][0] == len(matrix) - 1 or\
                    core[index][1] == 0 or core[index][1] == len(matrix) - 1:
                backtrack(visit, index + 1, total_line, total_core + 1)
            else:
                for i in range(4):
                    if find_cross(core[index][0], core[index][1], i, visit):
                        cnt += 1
                        continue
                    tmp_visit = [vs[:] for vs in visit]
                    paint(core[index][0], core[index][1], i, tmp_visit)
                    tmp1 = electric_line[index][i]
                    backtrack(tmp_visit, index + 1, total_line + electric_line[index][i], total_core + 1)

                if cnt == 4:
                    backtrack(visit, index + 1, total_line, total_core)


    def find_cross(x, y, direction, visit):
        # cross 하는지만 확인
        delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        dx = x + delta[direction][0]
        dy = y + delta[direction][1]
        while 0 <= dx < len(visit) and 0 <= dy < len(visit):
            if visit[dx][dy] > -1:
                return True
            dx += delta[direction][0]
            dy += delta[direction][1]
        return False

    def paint(x, y, direction, visit):
        # 해당 방향으로 그림
        delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        dx = x + delta[direction][0]
        dy = y + delta[direction][1]
        while 0 <= dx < len(visit) and 0 <= dy < len(visit):
            visit[dx][dy] = 1
            dx += delta[direction][0]
            dy += delta[direction][1]


    backtrack(visited)
    print("#{} {}".format(tc, linked_line))

 

 

이문제 풀면서 네시간 정도 걸렸는데 처음엔 brute-force로 접근했다가 시간을 날려먹었고 이후에 정신을 차리고 backtracking으로 조합했다. 이것도 brute-force같다 ㅋㅋ

각 코어마다 사방으로 길이를 측정해서 모든 조합을 만들어내는 방식으로 접근했다.

조합을 만들때 코어의 전선들이 겹치는지 확인하고 겹치지 않는 경우에 전선을 새로 그려 다음 재귀함수로 넘겨주었다.

지금 다시 보니 사방의 길이를 구하는건 일을 여러번 하는 느낌이다. 

그리고 이번 문제를 풀면서 코드가 길어질수록 변수명이많이 헷갈린다는 것을 느꼈고,

deepcopy보다 인덱스로 복사하는게 훨씬 빠르다는 것을 알게 되었다.

 

하... 실력 안는다... 과연 코딩테스트를 통과할수 있을까?