삼성 SW Expert Academy 1767. [SW Test 샘플문제] 프로세서 연결 문제풀이

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf

SW Expert Academy

문제풀이:  이 문제의 핵심은 우선순위를 잘 생각해야 하는 것이다. 먼저 가장 많은 코어의 개수를 연결하는 것이 첫 번째 순위이고, 두 번째 순위는 코어의 개수가 같을 때, 전선의 길이가 최소일 때를 반환하는 것이다. 

제약사항은 다음과 같다.

[제약 사항]

1. 7 ≤  N ≤ 12
2. Core의 개수는 최소 1개 이상 12개 이하이다.
3. 최대한 많은 Core에 전원을 연결해도, 전원이 연결되지 않는 Core가 존재할 수 있다.

 

내가 푼 코드는 다음과 같다. 

 

 

 

# 몇개의 테스트 케이스를 받을 것인지 n으로 받는다.
n=int(input())
# 이번 문제의 핵심인 dfs를 구현하였다.
def dfs(check,core2,line2):
		#전역변수인 core와 line을 선언 
        global core
        global line
        # s는 각 케이스마다 주어진 코어의 개수이다.
        # check가 s와 같을 경우는 dfs가 모든 core를 체크하였을 때의 경우이다.
        if check==s:
        	# dfs로 탐색한 코어의 개수가 현재까지 탐색한 코어의 개수보다 많을 때
            if core<core2:
            	#코어의 개수를 갱신하여주고, 전선의 길이 역시 갱신한다.
                core=core2
                line=line2
                # 만약 코어의 개수는 같은데 전선의 길이가 짧아진 경우 전선의 길이를 갱신한다.
            elif core2==core:
                if line>line2:
                    line=line2
            return
        # 탐색이 끝까지 간 경우가 아닌 경우 cores에 담긴 코어의 좌표를 받아 x,y로 할당한다.
        x=cores[check][0]
        y=cores[check][1]
        # 코어에서 동 서 남 북 방향으로 체크하여 코어가 연결이 될 경우 연결시키고 다음 코어로 넘어간다.
        # 각 방향에서 되지 않을 경우 다음 방향으로 넘어간다.
        for i in range(4):
            if i==0:
                flag=0
                for i in range(x,0,-1):
                    if b[i-1][y]==1:
                        flag=1
                        break
                if flag==1:
                    continue
                else:
                    for i in range(x,0,-1):
                        b[i-1][y]=1
                        line2+=1
                    dfs(check+1,core2+1,line2)
                    for i in range(x,0,-1):
                        b[i-1][y]=0
                        line2-=1
            elif i==1:
                flag=0
                for i in range(y,a-1):
                    if b[x][i+1]==1:
                        flag=1
                        break
                if flag==1:
                    continue
                else:
                    for i in range(y,a-1):
                        b[x][i+1]=1
                        line2+=1
                    dfs(check+1,core2+1,line2)
                    for i in range(y,a-1):
                        b[x][i+1]=0
                        line2-=1
            elif i==2:
                flag=0
                for i in range(x,a-1):
                    if b[i+1][y]==1:
                        flag=1
                        break
                if flag==1:
                    continue
                else:
                    for i in range(x,a-1):
                        b[i+1][y]=1
                        line2+=1
                    dfs(check+1,core2+1,line2)
                    for i in range(x,a-1):
                        b[i+1][y]=0
                        line2-=1
            elif i==3:
                flag=0
                for i in range(y,0,-1):
                    if b[x][i-1]==1:
                        flag=1
                        break
                if flag==1:
                    continue
                else:
                    for i in range(y,0,-1):
                        b[x][i-1]=1
                        line2+=1
                    dfs(check+1,core2+1,line2)
                    for i in range(y,0,-1):
                        b[x][i-1]=0
                        line2-=1
        # 만약 4방향이 다 막혔을 경우 코어를 체크만 하고 넘어간다. 이것을 생각하기가 조금 어려웠다.
        dfs(check+1,core2,line2)
# n개의 케이스동안 반복한다.
for k in range(1,n+1):
	# 코어의 좌표를 받을 리스트를 만든다. 
    cores=[]
    core=0
    line=0
    a=int(input())
    # 멕시노스를 b라는 변수에 받는다.
    b= [list(map(int, input().split())) for _ in range(a)]
    # 각 코어의 좌표를 cores에 입력한다.
    for i in range(1,a-1):
        for j in range(1,a-1):
            if b[i][j]==1:
                cores.append([i,j])
    # 코어의 총 개수를 s에 담는다.
    s=len(cores)
    # dfs를 실행한다.
    dfs(0,0,0)
    # dfs로 탐색하여 최종결과를 프린트한다.
    print('#{} {}'.format(k,line))

생각보다 까다로운 문제지만, dfs의 개념을 정확히 알고 있는가를 묻는 문제였고, 많은 도움이 되었다.