[DFS] 점프

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

N * N 숫자판 A에서 개구리가 점프를 한다.
숫자판의 각 셀은 (0, 0) 에서 (n-1, n-1) 이라 한다.
개구리는 각 셀에 적혀 있는 숫자만큼 오른쪽이나 아래쪽으로 점프를 할 수 있다.
개구리는 (0, 0)에서 출발해서 (n-1, n-1)에 도착해야 한다.
정사각형 바깥으로는 점프할 수 없다.
N과 A의 각 셀의 숫자가 주어졌을 때, 개구리가 출발점에도 도착점으로 이동 가능한 지를 출력하시오.

Input
첫째 줄에 양의 정수 N이 주어진다.
둘째 줄부터 N개의 줄에 A의 각 행의 원소 N개가 한 줄에 하나씩 주어진다.
3
1 2 3
2 3 1
3 2 1

3
1 2 3
2 1 2
3 2 1
Output
첫째 줄에 개구리가 출발점에서 도착점까지 이동이 가능하면 "Yes"를 출력한다.
이동이 불가능하면 "No"를 출력한다.
Yes

No

 

# 개구리 탈출 성공: yes 
# 개구리 탈출 실패: no
import sys
input = sys.stdin.readline

# n*n 숫자판
n=int(input())
array = [list(map(int, input().split())) for _ in range(n)]

def dfs(x, y):
    down=False
    right=False
    if x==n-1 and y==n-1: # x=n-1 and y=n-1에 도착
        return True
    else:
        if x+array[x][y]<n: # 개구리 아래로 이동 & 정사각형 바깥으로는 점프할 수 없음
            down=dfs(x+array[x][y], y)
        if y+array[x][y]<n: # 개구리 오른쪽으로 이동 & 정사각형 바깥으로는 점프할 수 없음
            right=dfs(x, y+array[x][y])
    return down or right

if dfs(0, 0):
    print('Yes')
else:
    print('No')

---

# 개구리 경로 출력
import sys
input = sys.stdin.readline

# n*n 숫자판
n=int(input())
array = [list(map(int, input().split())) for _ in range(n)]

def dfs(x, y, s):
    down=False
    right=False
    if x==n-1 and y==n-1: # x=n-1 and y=n-1에 도착
        return s
    else:
        if x+array[x][y]<n: # 개구리 아래로 이동 & 정사각형 바깥으로는 점프할 수 없음
            down=dfs(x+array[x][y], y, s+"("+str(x+array[x][y])+ ","+str(y)+ ")"+" -> ")
        if y+array[x][y]<n: # 개구리 오른쪽으로 이동 & 정사각형 바깥으로는 점프할 수 없음
            right=dfs(x, y+array[x][y], s+"("+str(x)+ ","+str(y+array[x][y])+")"+" -> ")
    return down or right

# 개구리가 이동할 수 있으면 경로를 출력
if dfs(0, 0, ""):
    print(dfs(0, 0, ""))
# 개구리가 이동할 수 없으면 'No'를 출력
else:
    print('No')

 

 

 

 

---

개구리가 도착지점까지 갈 수 있는 경로 & 개구리가 도착지점까지 갈 수 있는 경우의 수 출력하고 싶다면....?

#  개구리가 갈 수 있는 모든 가능한 경우의 수 출력 & 개구리가 이동 할 수 있는 경우의 수 
import sys
input = sys.stdin.readline

# n*n 숫자판
n=int(input())
array = [list(map(int, input().split())) for _ in range(n)]
answer=[]
def dfs(x, y, s):
    down=False
    right=False
    if x==n-1 and y==n-1: # x=n-1 and y=n-1에 도착
        answer.append(s)
        return s
    else:
        if x+array[x][y]<n: # 개구리 아래로 이동 & 정사각형 바깥으로는 점프할 수 없음
            down=dfs(x+array[x][y], y, s+"("+str(x+array[x][y])+ ","+str(y)+ ")"+" -> ")
        if y+array[x][y]<n: # 개구리 오른쪽으로 이동 & 정사각형 바깥으로는 점프할 수 없음
            right=dfs(x, y+array[x][y], s+"("+str(x)+ ","+str(y+array[x][y])+")"+" -> ")
    return down or right

# 개구리가 이동할 수 있으면 경로를 출력
if dfs(0, 0, ""):
    print(dfs(0, 0, ""))
# 개구리가 이동할 수 없으면 'No'를 출력
else:
    print('No')

print("------------------------------------------------")
print("개구리가 점프할 수 있는 모든 가능한 경우의 수 출력")
answer = list(set(answer))
for i in range(len(answer)):
    print(answer[i])
print(len(answer))

Output
(1,0) -> (2,0) -> (2,1) -> (2,2) -> 
------------------------------------------------
개구리가 점프할 수 있는 모든 가능한 경우의 수 출력
(1,0) -> (1,1) -> (1,2) -> (2,2) -> 
(0,1) -> (1,1) -> (2,1) -> (2,2) -> 
(1,0) -> (2,0) -> (2,1) -> (2,2) -> 
(0,1) -> (0,2) -> (1,2) -> (2,2) -> 
(1,0) -> (1,1) -> (2,1) -> (2,2) -> 
(0,1) -> (1,1) -> (1,2) -> (2,2) -> 
6

---

경로 출력 코드2

# 경로 출력하는 코드2
N = int(input())

matrix = [list(map(int, input().split())) for _ in range(N)]
path = []
cnt=0

def DFS(cur_row, cur_col) :
    path.append((cur_row, cur_col))

    if(cur_row==N-1 and cur_col == N-1) :
        print("Yes", end= ' ')
        global cnt
        cnt+=1
        print(*path)

        #quit()

    next_row = cur_row + matrix[cur_row][cur_col]
    next_col = cur_col + matrix[cur_row][cur_col]

    if(next_row < N) :
        #path.append((next_row, next_col))
        DFS(next_row, cur_col)
        path.pop()

    if(next_col < N) :
        #path.append((next_row, next_col))
        DFS(cur_row, next_col)
        path.pop()


DFS(0,0)
print("No")

print(cnt)