프로그래머스 BFS/DFS 문제입니다. 알고리즘 숙달을 위한 문제 반복풀이입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1844

[나의 풀이1]

💥 효율성 테스트 실패 (25분 경과)

def solution(maps):

    x_len = len(maps)
    y_len = len(maps[0])

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

    from collections import deque

    queue = deque([(0,0,1)])

    while queue:

        x,y,n = queue.pop()

        if x==x_len-1 and y==y_len-1:
            return n

        maps[x][y] = -1

        for i in range(4):
            
            newX = x+dx[i]
            newY = y+dy[i]

            if newX>=0 and newX<x_len and newY>=0 and newY<y_len:
            
                if maps[newX][newY] == 1:
                    queue.appendleft((newX,newY,n+1))

    if n != -1:
        return -1

2차원 맵 내의 목적지까지 최단거리를 구하는 문제입니다. 그래프 탐색의 대표적인 문제 유형이며 이전에 풀었던 문제로 큰 틀은 어렵지 않게 구현할 수 있었습니다.

하지만 위 코드로는 효율성 테스트에서 시간초과가 발생하였습니다. 이유로는 다음으로 이동 가능한 newX,newY좌표를 appendleft하는 즉시 -1로 초기화하지 않다보니 다른 케이스의 다음 좌표에서 그 다음 위치를 탐색할 때 -1인지 모르기 때문에 일단 appendleft 하는 경우가 생겨 시간이 더 오래 걸리게 됩었습니다.

[나의 풀이2]

⌛ 소요 시간 35분

def solution(maps):
	
    # col 크기
    x_len = len(maps)
    # row 크기
    y_len = len(maps[0])

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

    from collections import deque
	
    # BFS 구현을 위한 queue 구조
    queue = deque([(0,0,1)])

    while queue:

        x,y,n = queue.pop()

        if x==x_len-1 and y==y_len-1:
            return n

        for i in range(4):
            
            newX = x+dx[i]
            newY = y+dy[i]

            if newX>=0 and newX<x_len and newY>=0 and newY<y_len:
            
                if maps[newX][newY] == 1:
                    maps[newX][newY] = -1
                    queue.appendleft((newX,newY,n+1))

    if n != -1:
        return -1

그리하여 방문한 좌표를 -1로 초기화 해주는 구문을 다음 이동 가능한 좌표로 발견한 즉시
maps[newX][newY] = -1 구문을 통해 초기화시켜 불필요한 확인을 줄일 수 있었습니다.

해당 문제는 DFS로 구현할 수도 있지만 DFS의 경우 모든 경로를 끝까지 탐색하기 때문에 BFS로 구현하는 것이 포인트였고

또, BFS 구조를 통해 queue 구조에 (x좌표, y좌표, 움직인 횟수(n))을 appendleft하여 구현하였습니다.

[다른 사람의 풀이1]

from collections import deque

def solution(maps):
    if len(maps) == 1 and len(maps[0]) == 1:
        return 1
    row_len = len(maps)
    vec_len = len(maps[0])
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    # 맵 받기
    def bfs():
        queue = deque()
        queue.append((0, 0))
        
        while queue:
            row, vec = queue.popleft()
            if (row, vec) == (row_len - 1, vec_len - 1):
                return maps[row][vec]
            for (y, x) in zip(dy, dx):
                new_row = row + y
                new_vec = vec + x
                if new_row < 0 or new_row >= row_len or \
                    new_vec < 0 or new_vec >= vec_len or \
                    maps[new_row][new_vec] == 0 or \
                    (maps[new_row][new_vec] != 1 and 
                     maps[new_row][new_vec] <= maps[row][vec] + 1):
                    continue
                maps[new_row][new_vec] = maps[row][vec] + 1
                queue.append((new_row, new_vec))
        return -1

    return bfs()

저의 풀이와 유사한 구조이지만 최단거리를 구하는 문제이기 때문에 지나온 거리마다 +1 하여
목적지에 도달했을 때 해당 위치의 좌표롤 답을 도출하는 풀이입니다.

또한 이동할 수 있는지 여부를 판단할 때의 조건문 표현을 조금 다르게 하였습니다. 다음 x or y좌표가 맵을 벗어날때나 벽일 때, 다음위치가 이미 지나온 위치이기 때문에 현재 좌표값이 더 클 때의 케이스는 continue하여 appned 하지않는 방식입니다.

[다른 사람의 풀이2]

from collections import deque
def solution(maps):
    n = len(maps); m = len(maps[0])
    visited = [[False]*m for _ in range(n)]
    q = deque()
    q.append((0, 0))
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    visited[0][0]=True
    while q:
        y, x = q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<m and 0<=ny<n and maps[ny][nx] == 1:
                if not visited[ny][nx]:
                    visited[ny][nx] = True
                    q.append((ny, nx))
                    maps[ny][nx] = maps[y][x]+1
    if maps[n-1][m-1]==1:
        return -1
    else:
        return maps[n-1][m-1]

위 풀이는 BFS구조 , visited 리스트를 통해 방문 여부를 판별한 코드입니다. 또한 '다른 사람의 풀이1'과 같이 지나온 좌표에 +1씩하여 움직인 거리를 표기한 방식이었습니다.

감사합니다.