[백준2210] / 숫자판 점프 - DFS (백트래킹을 곁들인...)

 

백준2210

 

 

푼 날짜 : 2024.10.30

푼 문제 : [2210] / 숫자판 점프

사용한 언어 : python

알고리즘 : DFS

 

 

접근 방식 :

깊이 우선 탐색으로 시작한다.

문자열을 하나씩 추가해가며 여섯 자리가 만들어지면 set에 담겨 있는지 확인하고 없다면 추가한다. 

(여섯 자리가 만들어지면 무조건 리턴해준다.)

 

DFS를 다 돌고 나면 맨 뒤에 문자열을 제거한다.

이 과정을 반복하면 set에 중복없는 여섯 자리 수가 남게 된다!

 

 

코드 : 

NUM = 5 # 5x5 배열이므로 상수 고정

graph_ = []
for _ in range(NUM):
    nums = list(input().rstrip().split())
    graph_.append(nums)

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

# 가능한 경우의 수를 담기 위함
mySet = set()

def DFS(v, str_):

	# 여섯 자리 수 만들어졌을 때
    if len(str_) == 6:
    	# 이미 만들어진 수가 아니라면 추가
        if str_ not in mySet: mySet.add(str_)
        return

    for i in range(4):
        ny, nx = v[0]+dy[i], v[1]+dx[i]
        if 0<=ny<NUM and 0<=nx<NUM:
            str_ += graph_[ny][nx] # 현재 값 더하기
            DFS((ny, nx), str_)
            str_ = str_[:-1] # 맨 마지막 값 다시 빼주기

for i in range(NUM):
    for j in range(NUM):
        str_ = graph_[i][j]
        DFS((i, j), str_)

# 경우의 수 출력
print(len(mySet))

 

 

 

1트 성공 !!!! 뿌듯하다 오와아아아!!!!!

너무 기뻐 !!!!