[Softeer / Level3][HSAT 7회 정기 코딩 인증평가 기출] 순서대로 방문하기

https://softeer.ai/practice/info.do?idx=1&eid=2050 

Softeer

---

 

 

주어진 조건에 따라 정해진 위치를 방문해야하는 그래프 문제이다.

인덱스에 따라 움직이도록 종료조건을 걸어주고, 마지막 인덱스가 나온다면 카운트 값만 증가시키고 리턴.

주의해야할 점은 방문체크를 하고 나올 때 다시 방문해제를 해주어야 한다는 것이다.

 

 

<내 코드>

import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())

def is_valid(i, j):
    if i <= -1 or i >= N or j <= -1 or j >= N:
        return False
    if visited[i][j] or S[i][j] == 1:
        return False
    return True

def dfs(now, destIdx):
    global cnt
    if now == P[destIdx]:
        if destIdx == M - 1: #만약 마지막이면 카운트 값만 증가시키고 리턴시킨다.
            cnt += 1
            return
        else:
            destIdx += 1
    x, y = now
    visited[x][y] = 1 # 들어간곳 방문체크 한다.
    dxs, dys = [-1, 0, 1, 0], [0, 1, 0, -1]
    for dx, dy in zip(dxs, dys):
        new_x, new_y = x + dx, y + dy
        if is_valid(new_x, new_y):
            dfs((new_x, new_y), destIdx)
    visited[x][y] = 0 # 들어갔다가 나오면서 방문한곳을 모두 해제한다.
    return

S, P = [], []
q = deque()

for _ in range(N):
    S.append(list(map(int, input().split())))

visited = [[0 for _ in range(N)] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    P.append((a, b))

global cnt
cnt = 0
dfs(P[0], 1) #첫번째 P부터 시작, destination Index
print(cnt)