[dfs/백준] 2210번 : 숫자판 점프

- 문제 : https://www.acmicpc.net/problem/2210

 

Silver Level2 문제

행렬의 크기가 5x5라서 완전탐색을 하면서 각 위치에서 5번 이동해서 만든 6자리 수를 비교하려고 했다

 

처음에는 global temp를 선언한뒤 움직일때마다 숫자를 temp에 붙이는 식으로 생각했는데, 

dfs로 진행하다보니 그렇게 하면 하나의 케이스를 온전히 못 담기도 하고, 메모리 초과가 난다 

 

그래서 하나의 깊이마다 temp를 담기 위해 temp 파라미터를 추가한 후 그 길이가 6일 때 dfs를 멈춘다 

중복된 숫자를 넣지 않는 방법은 다음 코드를 작성하면 된다 

if not temp in answer:

 

다음에서 return을 두번째 if 안에서 안 하고, 첫번째 안에서 하는지 궁금했다. 

생각해보니까, 일단 길이가 6이 되면 그 탐색은 끝나는건데, 중복된 것이 있으면 answer에 넣지 않은 상태에서 끝나는거고, 중복된 것이 없으면 answer에 삽입하고 끝나는 거니까 그 두가지 경우를 모두 생각해서 return의 위치가 정해진 것 같다. 

만약 두번 째 if 안에 return이 있으면 중복된 경우 멈추지 않으니까 (내 생각이고, 틀릴 수도 있다)

이 생각을 기반으로 정답 풀이 코드를 조금 고쳤다. 이렇게 작성해도 정답이 뜬다 

if len(temp)==6:
        if not temp in answer:
            answer.append(temp)
        return

 

- 정답 풀이 :

 

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

data=[]
for _ in range(5):
    data.append(list(input().split()))
dx=[-1,1,0,0]
dy=[0,0,-1,1]
answer=[]

def dfs(x,y,temp):
    if len(temp)==6:
        if temp not in answer:
            answer.append(temp)
            return
        else: #중복되는 결과는 그냥 반환하기 
            return   
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<5 and 0<=ny<5:
            num=temp+data[nx][ny]
            dfs(nx,ny,num)

for i in range(5):
    for j in range(5):
        dfs(i,j,data[i][j])
        
print(len(answer))

 

- 시도해본 풀이 :

메모리 초과로 실패했다 

 

import sys
sys.setrecursionlimit(10**6)

data=[]
for _ in range(5):
    data.append(list(input().split()))

dx=[-1,1,0,0]
dy=[0,0,-1,1]
answer=[]
temp=''

def dfs(x,y):
    global temp
    if len(temp)==6:
        return temp    
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<= nx < 5 and 0 <= ny < 5 :
            temp += data[nx][ny]
            dfs(nx,ny)
            
for i in range(5):
    for j in range(5):
        result=dfs(i,j)
        if result not in answer:
            answer.append(result)
            
print(len(answer))