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

SW Expert Academy 1227: 미로2

SW Expert Academy

 

---

- 문제

 

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

---

- 풀이

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

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

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

            if 0 <= ni < 100 and 0 <= nj < 100:           # 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(100)]  # 100줄의 미로를 maze에 저장
    visited = [[0]*100 for _ in range(100)]               # 방문 여부도 100*100으로 만들기

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

    for i in range(100):
        for j in range(100):
            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로 문제를 풀어보았다. 

  

  이전에 1266번 : 미로1의 문제에서 크기만 100으로 늘어났을 뿐인데, 미로의 크기를 변형했더니 그대로 Pass가 되었다. 메모리를 얼마나 효율적으로 다루냐에 관한 문제인 것 같은데, 이전에 만들 때도 시간복잡도가 최소화되도록 만들다 보니 그대로 제출이 되었다.

 

  만약 pop할때 pop(0)같이 사용했다면 통과가 안 될 수도 있을 것 같다. pop(0)의 경우에는 O(n)인데 비해 pop()은 O(1)이기 때문이다.

 

---

- 기억할 것!

  시간복잡도를 언제나 염두해두고 코딩할 것!