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

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

 

쉬운 문제였는데 잘 안풀렸던 문제. 재귀를 돌려야해서 동작 예측을 하는게 어려웠던 것 같다. 

문제 풀 때 고민했던 건 1. 지나갈 때 만나는 숫자는 어디에 입력하는 것이고 2. 딱 5번만 이동은 어떻게 하는지 

 

-정답풀이: 

2번의 해답은 문자 길이가 6이고, result안에 없는 문자라면 result에 삽입하고 return을 한다 

def dfs(x,y,num):
    if len(num)==6:
        if not num in result:
            result.append(num)
        return

 

1번의 해답은 위치를 알려주는 x,y 말고 num이라는 파라미터를 더 추가해서 이 숫자에 저장하면서 진행하면된다. 

한칸씩 진행할 때마다 num에는 숫자가 쌓일 것이고, 이 길이가 6이 된다면 result에 넣고 끝난다 

def dfs(x,y,num):
    if len(num)==6:
        if not num in result:
            result.append(num)
        return  

    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<5 and 0<=ny<5:
            ans= num+s[nx][ny]
            dfs(nx,ny,ans)
            
s=[list(input().split()) for _ in range(5)]
result=[]
dx=[-1,1,0,0]
dy=[0,0,-1,1]

for i in range(5):
    for j in range(5):
        dfs(i,j,s[i][j])
        
print(len(result))