Coding 공부

import sys
sys.setrecursionlimit(10000)
def input():
    return sys.stdin.readline().rstrip()

def checkFreinds(target_node,friend):

    for node in friend:
        if not friendly[node][target_node]:
            return False
    return True

def dfs(node,friend):
    global K,result
    if len(friend) == K:
        result = list(map(str,friend))
        sys.stdout.write('\n'.join(result))
        exit(0)
        return

    for next_node in range(node+1,N+1):
        if friend_cnt[next_node] < K-1:
            continue
        if visited[next_node]:
            continue
        if not friendly[node][next_node]:
            continue
        if not checkFreinds(next_node,friend):
            continue
        visited[next_node] = True
        dfs(next_node,friend +[next_node])
        visited[next_node] = False



K,N,F = map(int,input().split())

friendly = [[False for _ in range(N+1)] for _ in range(N+1)]

friend_cnt = [0 for _ in range(N+1)]
for _ in range(F):
    x,y = map(int,input().split())
    friendly[x][y] = True
    friendly[y][x] = True
    friend_cnt[x] += 1
    friend_cnt[y] += 1

result = []
visited = [False for _ in range(N+1)]
for num in range(1,N+1):
    if friend_cnt[num] < K-1:
        continue
    visited[num] = True
    dfs(num,[num])
    visited[num] = False

print(-1)

 이 문제는 N명 중 K명의 소풍을 보내는 것이다. 

단 조건이 모두가 서로 친구여야한다는 것이다.

그래서  N*N 친구의 관계를 나타내는 freiendly라는 행렬을 만들어 두었다.

서로 간에 친구관계이면 True 아니면 False가 되도록 했다.

이렇게 사전 준비 작업을 했다면, 백트래킹으로 문제를 접근하면 된다.

이 문제의 출력 조건은 만족하는 K명의 소풍을 갈수 있는 조합이 많으면 사전순으로 출력하는 것이다.

그러면 우리는 1번 학생부터 순차적으로 접근을 해서 만족을 하는 첫번째 K명의 조합이 사전 순으로 가장 빠른다는 것을 알 수 있게 된다.

여기서 재귀로 할때 주의를 해야할 것이 몇가지가 있다.

먼저. 현재 방문하는 친구의 친구 숫자가 K-1보다 작으면 자기를 포함해서 세도 K명이 안되기에 pass를 해주어야한다.

그리고, 문제의 조건 중에 소풍을 가는 친구들은 모두 친구관계 이어야한다.

그러므로, checkFriends 라는 함수를 통해 지금까지 뽑은 friend와 새로 방문한 next_node와 친구관계인지 파악을 해준다.

단 하나라도 만족하지 않으면 False를 반환해주면 된다.

그 뒤에는 DFS 처럼 백트래킹을 해주면 된다.

그리고, K를 만족하는 friend 조합이 나오면 exit로 파일을 종료하게 해준다.

def dfs(x,y,cnt):
    global result
    if cnt > result:
        return
    if x >= 10:
        result = min(result,cnt)
        return
    if y >= 10:
        dfs(x+1,0,cnt)
        return
    if arr[x][y] == 1:
        for paper_size in range(5,0,-1):
            if paper[paper_size]:
                if x + paper_size <= 10 and y + paper_size <= 10:
                    flag = False
                    for dx in range(paper_size):
                        for dy in range(paper_size):
                            if not arr[x+dx][y+dy]:
                                flag = True
                                break
                        if flag:
                            break
                    if not flag:
                        for dx in range(paper_size):
                            for dy in range(paper_size):
                                arr[x+dx][y+dy] = 0
                        paper[paper_size] -= 1
                        dfs(x,y+paper_size-1,cnt+1)
                        paper[paper_size] += 1
                        for dx in range(paper_size):
                            for dy in range(paper_size):
                                arr[x+dx][y+dy] = 1
    else:
        dfs(x,y+1,cnt)

        


arr = [list(map(int,input().split())) for _ in range(10)]
paper = [0]+[5]*5
result = float('inf')
dfs(0,0,0)
print(result if result != float('inf') else -1)

def check(x,y,size):
    if x + size > 10 or y + size >10:
        return False
    for dx in range(size):
        for dy in range(size):
            if not arr[x+dx][y+dy]:
                return False
    return True


def set_position(x,y,size,val):
    for dx in range(size):
        for dy in range(size):
            arr[x+dx][y+dy] = val
def dfs(x,y,cnt):
    global result
    if cnt >= result:
        return
    finish = True
    while x < 10:
        while y < 10:
            if arr[x][y] == 1:
                finish = False
                for paper_size in range(5,0,-1):
                    if paper[paper_size] and check(x,y,paper_size):
                        set_position(x,y,paper_size,0)
                        paper[paper_size] -= 1
                        dfs(x,y+paper_size-1,cnt+1)
                        paper[paper_size] += 1
                        set_position(x,y,paper_size,1)
                return
            y += 1
        x += 1
        y = 0
    if finish:
        result = min(result,cnt)
        


arr = [list(map(int,input().split())) for _ in range(10)]
paper = [0]+[5]*5
result = float('inf')
dfs(0,0,0)
print(result if result != float('inf') else -1)