SWE(4875)_미로

작성일 | In

SWE 4875_미로

문제이해

NxM 미로. 출발지에서 목적지까지 도착하는 경로가 존재하는지 확인 2에서 출발 3에서 도착

도착가능 한지 여부 확인

해리님의 데브로그 코드 참고.

코드


# 상, 하, 좌, 우
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

visited = []  # 스택
result = 0
Maze = []


def IsSafe(y, x):  # 탐색 가능한지 확인
    return 0 <= y < N and 0 <= x < N and (Maze[y][x] == 0 or Maze[y][x] == 3)


def DFS(start_y, start_x):
    global result
    # 찾았다
    if Maze[start_y][start_x] == 3:
        result = 1
        return
    visited.append((start_y, start_x))  # 방문한 y,x 좌표 스택에 저장
    for dir in range(4):  # 이동하기
        New_Y = start_y + dy[dir]
        New_X = start_x + dx[dir]
        if IsSafe(New_Y, New_X) and (New_Y, New_X) not in visited:  # 안전하면서 방문하지 않은 노드라면,
            DFS(New_Y, New_X)


if __name__ == "__main__":
    T = int(input())

    for tc in range(1, T+1):
        N = int(input())
        # 이렇게 한번에 정수 입력 가능. 이건 기억하자
        Maze = [(list(map(int, input()))) for _ in range(N)]
        start_y = 0
        start_x = 0
        # 시작점 찾기
        for y in range(N):  # y축이 세로
            for x in range(N):  # x축이 가로
                if Maze[y][x] == 2:  # 시작점을 찾는다.
                    start_y, start_x = y, x
        result = 0
        visited = []  # 초기화
        DFS(start_y, start_x)
        print("#%d %d" % (tc, result))

참고자료 [해리의 데브로그]https://tothefullest08.github.io/algorithm/2019/03/07/6_4875_%EB%AF%B8%EB%A1%9C/

0%