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

💡문제

백준 2210번 문제 링크

🍀풀이

문제를 보자마자 아! dfs로 풀면 되겠다 생각했다.
하지만 너무 오랜만에 풀어서 헷갈려서 도움을 받아버렸다...

일단 한 번 거쳤던 칸을 다시 거쳐도 된다고 했으니 방문여부는 안해도 될거 같았고, 5x5니까 [0][0]부터 [4][4]까지 dfs를 해주면 된다!

grap = [list(map(str, input().split())) for _ in range(5)]	# 입력

result = []

def dfs(x, y, num):
    if len(num) == 6:	# 6자리이면 result에 저장
        result.append(num)
        return
    
    # 상하좌우
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >=5 or ny < 0 or ny >= 5:	# 범위 밖이면 무시
            continue
        else:
            dfs(nx, ny, num + grap[nx][ny])	# 문자열 더하고 dfs 시작

# [0][0]부터 [4],[4]까지 탐색
for i in range(5):
    for j in range(5):
        dfs(i, j, grap[i][j])
            
print(len(set(result)))	# set() 함수 사용해서 중복제거

BFS/DFS 마스터 하기 위해 조만간 문제 열심히 풀어봐야겠다.