[파이썬] 백준 2210 : 숫자판 점프

[파이썬] 백준 2210 : 숫자판 점프

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

2210번: 숫자판 점프

실버 2

그래프, DFS, 브루트포스

---

접근

 

방문처리를 할 필요가 없으므로 브루트포스와 같은 접근을 해야 한다.

모든 좌표에 대한 DFS를 진행하고, 글자 수를 하나씩 채우다가 길이가 6이 되는 경우 그 문자열이 기존에 추가했던 적이 있는지 없는지를 확인하고 리스트에 추가한다.

마지막으로 해당 리스트의 길이를 출력한다.

 

코드

import sys; input = sys.stdin.readline

def dfs(x, y, six_nums):
    six_nums += numbers[x][y]
    if len(six_nums) == 6:
        if six_nums not in result:
            result.append(six_nums)
        return
    else:
        for i in range(4):
            ndx = x + dx[i]
            ndy = y + dy[i]
            if 0 <= ndx < 5 and 0 <= ndy < 5:
                dfs(ndx, ndy, six_nums)
        
    

numbers = [list(input().split()) for _ in range(5)]
six_nums = ''
result = []
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
for i in range(5):
    for j in range(5):
        dfs(i, j, six_nums)
print(len(result))

 

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

dy = [0, 0 ,1 -1]

은 최초 지점에서 동서남북으로 한 칸씩 이동하는 모든 경우의 수를 담은 리스트이다.

 

for i in range(4):
            ndx = x + dx[i]
            ndy = y + dy[i]
            if 0 <= ndx < 5 and 0 <= ndy < 5:
                dfs(ndx, ndy, six_nums)

 

여기서 dx와 dy에 대한 인덱스가 똑같이 적용되기 때문에 (1,0), (-1,0), (0,1) (0,-1)씩 이동한 것으로 구현할 수 있는 것이다.

 

파이썬은 C++처럼 문자열끼리의 연산이 가능하다.

six_nums = ''으로 초기화했기에 좌표에 위치한 문자열 값을 그대로 더하는 방법으로 문자열을 합칠 수 있다.

 

def dfs(x, y, six_nums):
    six_nums += numbers[x][y]
    if len(six_nums) == 6:
        if six_nums not in result:
            result.append(six_nums)
        return

 

six_nums의 길이가 6이라면 해당 문자열이 result에 삽입되었던 적이 있는지 확인한다. 해당 없으면 그 문자열을 result에 삽입한다.

여기서의 six_nums는 dfs내에서만 값이 적용되는 지역변수이므로 return을 통해 함수가 종료되고 새로운 위치에 대한 dfs함수가 다시 호출될 때는 six_nums = ''의 값이 넘겨지게 된다.