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

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

2210번: 숫자판 점프

 

내 코드

import sys
input = sys.stdin.readline

graph = [list(input().split()) for i in range(5)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
ans =set()   
def dfs(x, y, res): 
    if len(res) == 6:
        ans.add(res)
        return

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx < 5 and 0<= ny < 5:
            dfs(nx, ny, res + graph[nx][ny])

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

 

코드 리뷰

이 문제를 처음 접근할 때 DFS 함수 인자에 배열을 넣어주지 않아서 자꾸 원하는 답이 나오지 않았다.

일반적인 DFS 로 풀면서도 주의해야 할 사항이 몇 가지 있다.

 

1. MAP(int, input()) 으로 넣지 않기

graph = [list(input().split()) for i in range(5)]

여기서 int 로 넣으면 안 되는데, 그 이유는 다음과 같다.

    if len(res) == 6:

dfs 안에 있는 함수다. int형으로 받아버리면, dfs를 종료하는 if문이 정상적으로 작동하지 않는다. int는 길이를 셀 수 없으므로 불가능하기 때문이다.

 

2. dfs 함수 안에서 배열도 같이 전달해주기

dfs(nx, ny, res + graph[nx][ny])

이 부분을 놓쳐서 계속해서 원하지 않는 답이 나왔다. 그리고 이건 위의 1번 조건을 지켜야 가능하다.

if len(ans) == 6:
	''.join(map(str,ans)

나는 처음에 이런 방법으로 풀었는데, 이는 if문을 한 번 더 쓰게 만들어서 시간복잡도만 조금 더 올릴 뿐만 아니라 코드도 조금 더 복잡해진다. 그래서 아예 res+graph[nx][ny]를 함으로써 애초에 string 처리를 통해 문자열을 받아버리는 것이다.

그리고 set에 만들어진 문자열을 넣으면 자동으로 중복 처리가 된다.