[2210] 숫자판 점프 in python

> DFS

 

set()을 이용해 중복을 잡아냈다.

실행시간은 약 94ms

 

array=[list(map(int,input().split())) for _ in range(5)]
result=set()
# 상,우,좌,하
dx=[-1,0,0,1]
dy=[0,1,-1,0]

def dfs(i,j,answer):
    if len(answer)==6:
        result.add(answer)
        return
    answer+=str(array[i][j])
    for k in range(4):
        nx=i+dx[k]
        ny=j+dy[k]
        if 0<=nx<5 and 0<=ny<5:
            dfs(nx,ny,answer)

for i in range(5):
    for j in range(5):
        answer=''
        dfs(i,j,answer)
print(len(result))

---

dx,dy 함수를 사용하지 않고

맵의 크기는 변화가 없으니까

if문으로 걸러내는 방법이

위 코드의 실행속도보다 더 빠름

array=[list(map(int,input().split())) for _ in range(5)]
result=set()

def dfs(i,j,answer):
    if len(answer)==6:
        result.add(answer)
        return
    answer+=str(array[i][j])
    if 0<=i-1:
        dfs(i-1,j,answer)
    if i+1<5:
        dfs(i+1,j,answer)
    if 0<=j-1:
        dfs(i,j-1,answer)
    if j+1<5:
        dfs(i,j+1,answer)

for i in range(5):
    for j in range(5):
        answer=''
        dfs(i,j,answer)
print(len(result))