미로1 Python(SW Expert Academy, SWEA)

난이도 : D4

문제번호 : 1226

문제 주소 및 출처입니다.

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

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

아래 그림과 같은 미로가 있다. 16*16 행렬의 형태로 만들어진 미로에서 흰색 바탕은 길, 노란색 바탕은 벽을 나타낸다. 가장 좌상단에 있는 칸을 (0, 0)의 기준으로 하여, 가로방향을 x 방향, 세로방향을 y 방향이라고 할 때, 미로의 시작점은 (1, 1)이고 도착점은 (13, 13)이다. 주어진 미로의 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 프로그램을 작성하라.

 

입력

각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다. 총 10개의 테스트케이스가 주어진다. 테스트 케이스에서 1은 벽을 나타내며 0은 길, 2는 출발점, 3은 도착점을 나타낸다.

출력

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

예시

입력

출력

1 1111111111111111 1210000000100011 1010101110101111 1000100010100011 1111111010101011 1000000010101011 1011111110111011 1010000010001011 1010101111101011 1010100010001011 1010111010111011 1010001000100011 1011101111101011 1000100000001311 1111111111111111 1111111111111111 2 1111111111111111 1200000010000011 1011111011111011 1000001010000011 1110101010111011 1010101010100011 1011111010111111 1000001010000011 1011101011111011 1010101010000011 1010101010111111 1010100000130011 1010111111111011 1000000000000011 1111111111111111 1111111111111111 ...

#1 1 #2 1 ...

---

2. 문제풀이

특정 지점에서 출발했을때 목표지점에 도착을 할 수 있는지 확인하는 문제이다. 이런경우 dfs 혹은 bfs를 이용하여 풀 수 있다. 특정지점을 찾는 것이기때문에 둘중 아무거나 써도 상관없다고 생각했다. 그렇지만 최단거리를 찾는다고 하면 bfs를 이용하여 풀면 더 빠르다. ------------------------------------------------------------------------------------------------------ dfs의 경우 이동이 가능하다면 재귀하는 형식으로 만들었으며(시스템 스택을 이용) 이전에 왔던길로 돌아가면 무한재귀가 되기때문에 지나왔던길은 벽(1)으로 표시하면서 간다. 진행을 못하면 돌아와서 갈림길에서 나눠질때의 순간으로 돌아오게 된다. 진행하는 위치에 목표지점(3)이 있다면 결과를 바꿔주고 리턴한다. ------------------------------------------------------------------------------------------------------ bfs의 경우 이동이 가능하다면 큐에 넣고 같은 범위를 진행하는 형식을 취하게 된다. 큐에 시작점을 넣어두고 큐가 빌때까지 반복을 하게되며 상하좌우로 봤을때 이동이 가능하면 큐에 넣는 방식으로 진행이 된다. 큐에 데이터를 꺼닐대 그 위치가 목표지점이라면 바로 종료를 하게된다. 여기도 bfs와 마찬가지로 갔던길을 다시 가지않기위해 갔던길은 벽으로 바꾼다.  밑에 dfs와 bfs의 풀이를 적어놓았다.

 

---

3. 소스코드

#D4 1226 미로1
 
#이동리스트
move_list = [(1, 0), (-1, 0), (0, 1), (0, -1)]
 
def dfs(y, x):
    global result
    #현재 위치가 도착점이라면
    #목표점에 도달했거나 결과가 이미나와있다면 리턴
    if map_list[y][x] == 3 or result:
        result = 1
        return
    for i, j in move_list:
        d_y = y + i
        d_x = x + j
        #반복하다가 결과가 나왔다면 리턴
        if result: 
            return
        #벽이아니거나 왔던 위치가 아니라면
        if map_list[d_y][d_x] != 1 :
            #현재위치를 벽으로 체크하고 재귀
            map_list[y][x] = 1
            dfs(d_y, d_x)
        
 
T = 10
for _ in range(T):
    t = int(input())
    N = 16
    map_list = [list(map(int, list(input()))) for _ in range(N)]
    result = 0
    #1,1 위치부터 탐색시작
    dfs(1,1)
    print('#{} {}'.format(t, result))
 

 

#D4 1226 미로1
from collections import deque 
 
#이동리스트
move_list = [(1, 0), (-1, 0), (0, 1), (0, -1)]
 
def bfs():
    queue = deque()
    queue.append((1, 1))
    map_list[1][1] = 1
    while len(queue):
        y, x = queue.popleft()
        if map_list[y][x] == 3:
            return 1
        map_list[y][x] = 1
        for i in move_list:
            my = i[0] + y
            mx = i[1] + x
            if 0 <= my < N and 0 <= mx < N and map_list[my][mx] != 1:
                queue.append((my, mx))
    return 0
 
 
for _ in range(10):
    t = int(input())
    N = 16
    map_list = [list(map(int, list(input()))) for _ in range(N)]
    #1,1 위치부터 탐색시작
    print('#{} {}'.format(t, bfs()))

 

아래가 dfs 위에가 bfs이다.