완전탐색 DFS 연습하기1(백준 16198번 2210번)

1. 문제

 

16198번: 에너지 모으기 (acmicpc.net)

16198번: 에너지 모으기

 

2. 풀이

 

기본적인 dfs 완전탐색 문제다

 

조건대로 구현하면 될 것같다

 

에너지 리스트에서 0번과 n-1번은 고를 수 없으니까 1번부터 n-2번까지 모두 골라본다

 

고른 번호가 k번이면.. k-1번과 k+1번의 원소를 곱해서 누적합을 시킨다

 

k번 원소를 삭제한다

 

dfs로 재귀호출

 

for k in range(1,w-1):

    de = e + (w_list[k-1]*w_list[k+1])

    w_list_copy = w_list[:]

    del w_list_copy[k]

    dfs(de,w-1,w_list_copy)

 

원소가 2개가 남는다면? 첫번째와 마지막은 고를 수 없다고 했잖아.

 

그러면 2개가 남았다면 더 이상 고를 수 없다는 말이다

 

그러면 에너지 최댓값인지 검사해서 갱신

from sys import stdin

def dfs(e,w,w_list):
    
    global max_e
    
    #남은 원소가 2개이면..
    #최댓값 갱신
    if w == 2:
        
        if max_e < e:
            
            max_e = e
    
    else:
        
        #1번부터 w-2번까지 모두 골라본다
        for k in range(1,w-1):
            
            #k번을 골랐을때, k-1번 원소랑 k+1번 원소의 곱을 누적합
            de = e + (w_list[k-1]*w_list[k+1])
            
            #원본은 남겨두고
            w_list_copy = w_list[:]
            
            #k번 원소를 삭제하고
            del w_list_copy[k]
            
            #재귀경로를 생성
            dfs(de,w-1,w_list_copy)

n = int(stdin.readline())

w_list = list(map(int,stdin.readline().split()))

max_e = 0

dfs(0,n,w_list)

print(max_e)

 

조금이라도 어렵게 느껴졌다면.. 연습이 여전히 부족했다는 뜻이다

 

 

3. 문제2

 

2210번: 숫자판 점프 (acmicpc.net)

2210번: 숫자판 점프

 

SWEA에서 풀어본 문제같은데..?

 

배열을 탐색하면서 가능한 모든 6자리 수를 만들어내는 문제

 

 

4. 풀이

 

역시 기본적인 DFS 완전탐색 문제다

 

배열의 모든 위치를 출발점으로 삼고

 

출발점부터 길이 6만큼만 DFS 탐색을 수행하고 만들어진 숫자를 set()에 넣는다

 

set()에 넣는건 당연히 중복을 제거하기 위해서

 

그리고 한번 간 곳을 다시 가도 된다니까 visited는 필요없다

 

길이가 제한되어있으니까.. visited없어도 충분히 가능하다고 생각했어야했다

 

from sys import stdin

def dfs(x,y,maps,s,num):
    
    global num_set

    if s == 5:
        
        num_set.add(num)
    
    else:

        for nx,ny in [[0,1],[1,0],[0,-1],[-1,0]]:
            
            dx = x + nx
            dy = y + ny

            if dx >= 0 and dx <= 4 and dy >= 0 and dy <= 4:

                dfs(dx,dy,maps,s+1,num+str(maps[dy][dx]))

maps = [list(map(int,stdin.readline().split())) for _ in range(5)]

num_set = set()

for y in range(5):
    
    for x in range(5):

        dfs(x,y,maps,0,str(maps[y][x]))

print(len(num_set))