[삼성sw 1767번] 프로세서 연결하기(파이썬)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf 

SW Expert Academy

(무단복제 이슈가 있어서

문제 일부만 캡쳐했습니다.)

core가 주어지고 core를 격자밖까지 이을 수 있다면

해결할 수 있는 문제.

 

이 문제를 보면

자연스럽게 백트레킹이 떠오릅니다.

예를들면 1번 core를 위쪽으로 연결했다면

2번 core는 좌로는 연결이 되지 않는 식이 발생할 수 있으니

1core 상->2core 하 ->3core 좌

             -->2core 상 -->3core 우

 

이런식으로 모든 케이스를 다 가정해야합니다.

# sw아카데미 1767 프로세서 연결하기
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def dfs(depth, cnt):
    global answer
    if depth == l_c:
        answer = min(answer, cnt)
        return

    cx, cy = core[depth]
    for d in range(4):
        nx = cx
        ny = cy
        flag = False
        tmp = set()
        # 상하좌우 살피면서 연결여부를 판단
        while True:
            nx += dx[d]
            ny += dy[d]
            # 범위벗어난다->연결이 되면 가능하다 표시하고 나가기
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                flag = True
                break
            # 코어를 만나면 못함
            if room[nx][ny] == 1:
                break
            # 다른 전선을 만나면 못함
            if visited[nx][ny] == True:
                break
            tmp.add((nx, ny))
        # 가능하다면 전선을 연결
        if flag:
            leng = 0
            for px, py in tmp:
                visited[px][py] = True
                leng += 1

            dfs(depth + 1, cnt + leng)

            for px, py in tmp:
                visited[px][py] = False


T = int(input())

for t in range(T):
    answer = 1e9
    N = int(input())
    room = []
    core = []
    for i in range(N):
        tmp = list(map(int, input().split()))
        for j in range(1, N - 1):
            if i == 0 or i == N - 1:
                break
            if tmp[j] == 1:
                core.append([i, j])
        room.append(tmp)
    l_c = len(core)
    visited = [[False] * N for _ in range(N)]

    dfs(0, 0)
    print("#%d %d" % (t + 1, answer))

처음에 제출한 코드입니다.

제출했더니 49번째 케이스에서 틀렸다고 떴습니다.

이유인즉,이런 케이스에서 막히는 거였습니다.

단순히 연결여부만 판단하고 넘겨주는 코드를 짰더니

저런 오류가 발생했습니다.

댓글을 보고 문제를 봤더니

'연결이 안된 core가 있을 수 있다'라는 대목을 봤습니다.

# sw아카데미 1767 프로세서 연결하기
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def dfs(depth, cnt, connect):
    global answer
    global max_connect
    if depth == l_c:
        if connect > max_connect:
            max_connect = connect

            answer = cnt
        elif connect == max_connect:
            answer = min(answer, cnt)
        return

    cx, cy = core[depth]
    for d in range(4):
        nx = cx
        ny = cy
        flag = False
        tmp = set()
        # 상하좌우 살피면서 연결여부를 판단
        while True:
            nx += dx[d]
            ny += dy[d]
            # 범위벗어난다->연결이 되면 가능하다 표시하고 나가기
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                flag = True
                break
            # 코어를 만나면 못함
            if room[nx][ny] == 1:
                break
            # 다른 전선을 만나면 못함
            if visited[nx][ny] == True:
                break
            tmp.add((nx, ny))
        # 가능하다면 전선을 연결
        if flag:
            leng = 0
            for px, py in tmp:
                visited[px][py] = True
                leng += 1

            dfs(depth + 1, cnt + leng, connect + 1)

            for px, py in tmp:
                visited[px][py] = False

        dfs(depth + 1, cnt, connect)


T = int(input())

for t in range(T):
    answer = 1e9
    max_connect = 0
    N = int(input())
    room = []
    core = []
    for i in range(N):
        tmp = list(map(int, input().split()))
        for j in range(1, N - 1):
            if i == 0 or i == N - 1:
                break
            if tmp[j] == 1:
                core.append([i, j])
        room.append(tmp)
    l_c = len(core)
    visited = [[False] * N for _ in range(N)]

    dfs(0, 0, 0)

    print("#%d %d" % (t + 1, answer))

수정한 코드.

이건 해당 케이스까지 고려해주지만

시간초과가 발생했습니다.

실제로 테스트케이스만 돌려도

좀 오래 걸리는 느낌이 들었던 코드.

이 부분은 구글링으로 힌트를 얻어

시간초과를 줄였습니다.

#sw아카데미 1767 프로세서 연결하기

dx=[0,0,1,-1]
dy=[1,-1,0,0]

def dfs(depth,cnt,connect):
    global answer
    global max_connect
    if depth==l_c:
        if connect>max_connect:
            max_connect=connect
            answer=cnt
        elif connect==max_connect and answer>cnt:
            answer=cnt
        return
    #이렇게 반복문 형태로 돌려주면서 시간초과 줄여줬습니다.
    for k in range(depth,l_c):
        cx,cy=core[k]
        for d in range(4):
            nx=cx
            ny=cy
            flag=False
            tmp=set()
            leng=0
            #상하좌우 살피면서 연결여부를 판단
            while True:
                nx+=dx[d]
                ny+=dy[d]
                #범위벗어난다->연결이 되면 가능하다 표시하고 나가기
                if nx<0 or nx>=N or ny<0 or ny>=N:
                    flag=True
                    break
                #코어를 만나면 못함
                if room[nx][ny]==1:
                    break
                #다른 전선을 만나면 못함
                tmp.add((nx,ny))
                leng+=1
            #가능하다면 전선을 연결
            if flag:
                for px,py in tmp:
                    room[px][py]=1
                #현재 연결한 코어 다음 코어로 넘어간다.
                dfs(k+1,cnt+leng,connect+1)

                for px,py in tmp:
                    room[px][py]=0


T=int(input())

for t in range(T):
    answer=1e9
    max_connect=0
    N=int(input())
    room=[]
    core=[]
    for i in range(N):
        tmp=list(map(int,input().split()))
        for j in range(1,N-1):
            if i==0 or i==N-1:
                break
            if tmp[j]==1:
                core.append([i,j])
        room.append(tmp)
    l_c=len(core)
    visited=[[False]*N for _ in range(N)]

    dfs(0,0,0)

    print("#%d %d"%(t+1,answer))

 

백트레킹에 대해서 공부하면서

어떻게 하면 시간초과를 줄일 수 있을지

생각하게 해준 좋은 문제입니다.