https://softeer.ai/practice/info.do?idx=1&eid=2050
주어진 조건에 따라 정해진 위치를 방문해야하는 그래프 문제이다.
인덱스에 따라 움직이도록 종료조건을 걸어주고, 마지막 인덱스가 나온다면 카운트 값만 증가시키고 리턴.
주의해야할 점은 방문체크를 하고 나올 때 다시 방문해제를 해주어야 한다는 것이다.
<내 코드>
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)
'Algorithm > Softeer' 카테고리의 다른 글
[Softeer / Level3] 강의실 배정 (1) | 2023.10.17 |
---|---|
[Softeer / Level3] 성적 평균 (0) | 2023.10.16 |
[Softeer / Level3][HSAT 7회 정기 코딩 인증평가 기출] 자동차 테스트 (1) | 2023.10.13 |
[Softeer / Level3]우물 안 개구리 (0) | 2023.10.08 |
[Softeer / Level2] GBC (1) | 2023.10.08 |