[python] SWEA - 1226. [S/W 문제해결 기본] 7일차 - 미로1

🤔문제 해결

1. D4 | DFS

2. 시작점을 찾는다.

3. 스택을 활용하고 상하좌우 4방향 탐색(인덱스 범위 이내)을 한다.

 (1) 길('0')을 만날 경우 스택에 추가하고, 나중에 다시 탐색하는 것을 방지하기 위해 그 지점의 값을 바꿔준다.

 (2) 끝('3')을 만날 경우 미로가 가능하다는 의미 이므로 답을 1로 하고 탐색을 종료한다.

 

💨 DFS 기본문제이다.

 

💻소스 코드

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
for _ in range(10):
    answer = 0
    n = int(input())
    maps = [list(input()) for _ in range(16)]

    # 출발점 찾기
    x, y = 0, 0
    for i in range(16):
        for j in range(16):
            if maps[i][j] == '2':
                x, y = i, j

    # 미로탐색 DFS
    stack = [(x, y)]
    while stack:
        cx, cy = stack.pop()
        for k in range(4):
            nx = cx + dx[k]
            ny = cy + dy[k]
            if 0 <= nx < 16 and 0 <= ny < 16:
                # 길을 만날 경우
                if maps[nx][ny] == '0':
                    stack.append((nx, ny))
                    maps[nx][ny] = '9'
                # 끝점을 만날 경우 
                elif maps[nx][ny] == '3':
                    answer = 1
                    stack.clear()
                    break

    print('#{} {}'.format(n, answer))

 

출처: SW Expert Academy

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14vXUqAGMCFAYD&categoryId=AV14vXUqAGMCFAYD&categoryType=CODE

SW Expert Academy

📕문제 확인하기🔻🔻

아래 그림과 같은 미로가 있다. 16*16 행렬의 형태로 만들어진 미로에서 흰색 바탕은 길, 노란색 바탕은 벽을 나타낸다.

가장 좌상단에 있는 칸을 (0, 0)의 기준으로 하여, 가로방향을 x 방향, 세로방향을 y 방향이라고 할 때, 미로의 시작점은 (1, 1)이고 도착점은 (13, 13)이다.

주어진 미로의 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 프로그램을 작성하라.

아래의 예시에서는 도달 가능하다.

 

 

 

아래의 예시에서는 출발점이 (1, 1)이고, 도착점이 (11, 11)이며 도달이 불가능하다.

[입력]

각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트케이스가 주어진다.

테스트 케이스에서 1은 벽을 나타내며 0은 길, 2는 출발점, 3은 도착점을 나타낸다.

[출력]

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도달 가능 여부를 1 또는 0으로 표시한다 (1 - 가능함, 0 - 가능하지 않음).