[백준/Python] 2210번(DFS, 브루트포스)_숫자판 점프

📌문제 유형

그래프 이론, 브루트포스 알고리즘, 그래프 탐색, DFS(실버2)

 

📌문제

2210번: 숫자판 점프

 

📌나의 문제풀이

- 실패 

graph = []
num_list = []

for i in range(5):
    graph.append(list(map(int,input().split())))

def dfs(graph,cnt,ans,x,y):
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        # 여기서 오류
        cnt += 1
        if nx > 0 and nx < len(graph) and ny > 0 and ny < len(graph[0]):
            ans += str(graph[nx][ny])

            if len(ans) == 6 and cnt == 6:
                if ans not in num_list:
                    num_list.append(ans)
                    return
            
            if cnt < 6:
                dfs(graph,cnt,ans,nx,ny)
            else:
                return

for i in range(len(graph)):
    for j in range(len(graph[0])):
        dfs(graph,0,'',i,j)
print(num_list)
print(len(num_list))

- 다른사람 코드 참고하여 성공

graph = []
num_list = []

for i in range(5):
    graph.append(list(map(int,input().split())))

def dfs(graph,ans,x,y):
    if len(ans) == 6:
        if ans not in num_list:
            num_list.append(ans)
        return

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

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < 5 and 0 <= ny < 5:
            dfs(graph,ans + str(graph[nx][ny]),nx,ny)

for i in range(5):
    for j in range(5):
        dfs(graph,'',i,j)
        
print(len(num_list))

 

📌 다른사람의 문제풀이

#380 백준 파이썬 [2210] 숫자판 점프 - DFS

def dfs(x, y, number):
    if len(number) == 6: #6자리 숫자가 만들어졌다면
        if number not in result: #result에 없다면
            result.append(number)
        return
        
    dx = [1, -1, 0, 0] #상하좌우 확인 x
    dy = [0, 0, 1, -1] #상하좌우 확인 y
    for k in range(4):
        ddx = x + dx[k]
        ddy = y + dy[k]
        
        if 0 <= ddx < 5 and 0 <= ddy < 5: #범위 내에 있다면
            dfs(ddx, ddy, number + matrix[ddx][ddy]) #6글자가 될 때 까지 재귀

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

result = []
for i in range(5):
    for j in range(5):
        dfs(i, j, matrix[i][j]) #0,0부터 4,4까지 모두 검사
print(len(result))

 

📌 리뷰 

- Q1) 문자 길이 6 확인하는 과정이 좌표변환 과정 안에 있으면?

• for문 안에서 함수가 끝나는 거라, 다른 for문 값을 확인 안하고 건너 뛸 수 있음
• DFS 종료하는 과정은, 함수 초입에 검사해주기!!!

- Q2) 좌표 범위가 5안에 있고,  ans  += str(graph[nx][ny]) dfs(graph, ans, nx,ny)를 하면 회귀 오류가 되는 경우는?

• ans  += str(graph[nx][ny]) 해당 형태로 넘겨주면 같은 depth에서 숫자 갱신이 안되서 오류남
• 다시 돌아올 수 있는 경우, ans  + str(graph[nx][ny]) 값 자체를 다 넘겨주기(갱신 안되는 형태로!)

[leet22] DFS 인자를 할당된 객체가 아닌 직접 지정해줘야 하는 경우

# 오류
if 0 <= nx < 5 and 0 <= ny < 5:
    ans += str(graph[nx][ny])
    dfs(graph,ans,nx,ny)
    
# 오류 아님
if 0 <= nx < 5 and 0 <= ny < 5:
    dfs(graph,ans + str(graph[nx][ny]),nx,ny)