SWEA 1226 : 미로1(S/W 문제해결 기본)[파이썬]

SW Expert Academy 1266: 미로1

SW Expert Academy

 

---

- 문제

  입구와 출구가 주어지고 0으로 길이 나있으면 이 길을 따라가면 출구에 도착할 수 있는지 여부를 확인하는 문제다.

---

- 풀이

def bfs(x, y):
    check = 0
    temp = [[x, y]]                                     # 시작지점을 temp에 넣고
    visited[x][y] = 1                                   # 시작지점의 방문여부 True

    while True:
        i, j = temp.pop()                               # 스택이라고 생각하고 FILO(First in last out)

        for dir in range(4):                            # 상하좌우 네 가지 방향에 따라 반복
            ni = i + directionX[dir]
            nj = j + directionY[dir]

            if 0 <= ni < 16 and 0 <= nj < 16:           # maze의 크기를 벗어나지 않도록
                if maze[ni][nj] == 0 and visited[ni][nj] == 0:  # 방문한적이 없고 길이 있으면 해당 길을 temp에 저장
                    temp.append([ni, nj])
                    visited[ni][nj] = 1
                elif maze[ni][nj] == 3:                 # 출구면 break
                    check = 1
                    break
        if check == 1 or len(temp) == 0:
            break
    return check


directionX = [-1, 1, 0, 0]
directionY = [0, 0, -1, 1]

for t in range(10):                                     # 여기가 시작점
    nothing = input()                                   # 필요없는 숫자 하나 입력받아주고
    maze = [list(map(int, input()))for _ in range(16)]  # 16줄의 미로를 maze에 저장
    visited = [[0]*16 for _ in range(16)]               # 방문 여부도 16*16으로 만들기

    x = -1                                              # 시작지점 찾기
    y = -1

    for i in range(16):
        for j in range(16):
            if maze[i][j] == 2:
                x = i
                y = j
                break
        if x != -1:
            break
    answer = bfs(x, y)                                  # 너비우선탐색 시작
    print("#{} {}".format(t+1, answer))

 

  BFS(너비우선탐색)와 DFS(깊이우선탐색)의 두가지 방법으로 문제를 해결할 수 있지만, 재귀함수로 만들지 않고 풀기에는 BFS가 더 편하므로 BFS로 문제를 풀어보았다. 

  

  temp라는 임의로 만든 스택(리스트이지만, 스택이라고 생각해서 pop을 해야 시간복잡도가 적다)이 비어버릴 때까지 미로를 탐색하다가 temp가 비어버리거나 출구를 찾았을 때 끝내도록 하였다.

---

- 기억할 것!

maze = [list(map(int, input()))for _ in range(16)]

  위와 같은 방식으로 16줄의 입력을 받을 수 있다!