[Python] 2210번 숫자판 점프

https://www.acmicpc.net/problem/2210

 

dx=[-1,0,0,1]
dy=[0,-1,1,0]

def dfs(j,i,tmp): #dfs(0,0,[])
    if len(tmp)==6:
        t=''
        for ti in tmp:
            t+=ti
        if t not in res:
            res.append(t)
    
    for d in range(4):
        nx=i+dx[d]
        ny=j+dy[d]
        if 0<=nx<5 and 0<=ny<5:
            if len(tmp)<6:
                tmp.append(board[ny][nx])
                dfs(ny,nx,tmp)
                tmp.pop() #백트레킹!!! (빠졌던 부분)

board=[]
for _ in range(5):
    board.append(list(map(str,input().split())))
    
res=[] #정답을 위한 리스트 -> res 안의 동일한 숫자면 추가하지 않는다
tmp=[] #6자리 수인지 확인

for j in range(5):
    for i in range(5):
        dfs(j,i,[board[j][i]])
          
print(len(res))

 

처음에 코드를 짰을 때 분명 될 것 같았는데 안 되길래 결국 GPT로 확인해보니 백트레킹을 안 넣어 오류가 발생한 것이였다. (새삼 또 GPT가 최고다,,,,) 아무튼 백트레킹을 추가하니 문제가 풀렸다!

 

위에 코드로도 통과는 하였지만 재귀함수를 더 빨리 빠져나올 수 있도록 return을 추가해보았다.

dx=[-1,0,0,1]
dy=[0,-1,1,0]

def dfs(j,i,tmp): #dfs(0,0,[])
    if len(tmp)==6:
        t=''
        for ti in tmp:
            t+=ti
        if t not in res:
            res.append(t)
        return #추가한 부분
    
    for d in range(4):
        nx=i+dx[d]
        ny=j+dy[d]
        if 0<=nx<5 and 0<=ny<5:
            if len(tmp)<6:
                tmp.append(board[ny][nx])
                dfs(ny,nx,tmp)
                tmp.pop() #백트레킹!!! (빠졌던 부분)

board=[]
for _ in range(5):
    board.append(list(map(str,input().split())))
    
res=[] #정답을 위한 리스트 -> res 안의 동일한 숫자면 추가하지 않는다
tmp=[] #6자리 수인지 확인

for j in range(5):
    for i in range(5):
        dfs(j,i,[board[j][i]])
          
print(len(res))

 

속도가 쪼금 더 빨라 진 것을 볼 수 있었다.

 

기억하자! 

재귀함수를 쓸 때는 return문!!