[자바] SWEA 1767 : 프로세서 연걸하기 (test)

[자바] SWEA 1767 : 프로세서 연걸하기 (test)

• SWEA 1767 : 프로세서 연걸하기

---

풀이

방향성 생각

• 백트래킹
• 맵이 작아서 맵에 간선을 깔면서 진행한다.
• 종료 조건만 잘 적어주고, 간선까는건 단순 for문이라 인덱스 실수만 안하면 된다.

 

전체코드

from collections import defaultdict as dd

inside = lambda x,y : 0<=x<N and 0<=y<N
border = lambda x,y : x==0 or x==N-1 or y==0 or y==N-1
dires = [(1,0),(0,1),(-1,0),(0,-1)]

def dfs(idx,cnt,leng):

    # 도착하면 개수에 길이 추가
    if idx == L:
        answer[cnt].add(leng)
        return

    x,y = locs[idx]
    for dx,dy in dires:
        flag = True
        step = 0

        # 앞에 레일에 깔 수 있으면 step만큼 깔아주기
        for s in range(1,N+1):
            nx,ny = x+dx*s, y+dy*s

            if not inside(nx,ny): 
                break

            if arr[ny][nx]: 
                flag = False
                break

            step += 1

            if border(nx,ny): 
                break

        # 깔 수 있는 경우 탐색진행
        if flag:  
            for s in range(1,step+1):
                nx,ny = x+dx*s, y+dy*s
                arr[ny][nx] = 1

            dfs(idx+1,cnt+1,leng+step)

            for s in range(1,step+1):
                nx,ny = x+dx*s,y+dy*s
                arr[ny][nx] = 0
    # 깔지 않는 경우
    dfs(idx+1,cnt,leng)

TC = int(input())
for tc in range(1,TC+1):
    N = int(input())
    arr = [list(map(int,input().split())) for _ in range(N)]
    locs = [(j,i) for i in range(N) for j in range(N) if arr[i][j] and not border(j,i)]
    L = len(locs)

    answer = dd(set)
    dfs(0,0,0)
    print(f"#{tc} {min(answer[max(answer.keys())])}")

코멘트

• 백트래킹에서 실수하지 않게 주석 자세하게 작성하면서 풀기