[스파르타] 99클럽 2기 코테스터디 12일차 TIL / 게임 맵 최단거리

프로그래머스: 게임 맵 최단거리 (링크)

 

동, 서, 남, 북으로 1칸씩 이동하고 최단거리를 구하는 문제여서 바로 BFS로 풀었다. 다만 처음에 문제를 잘못 이해해서 n, m이 예시 문제에 있는 5로 고정되어 있는 줄 알았고 결국 다시 풀었다. 주어지는 건 2차원 배열인 maps 뿐이라 행과 열의 개수를 직접 구해야 했다. BFS 문제는 전형적인 틀이 있는데 거기에서 크게 벗어나는 부분이 없었다. 최단 거리를 구해야 하므로 그냥 바로 직전 지점의 +1 값을 계속 갱신하는 부분만 추가했다. 

 

다른 사람들의 풀이를 보니까 다들 BFS로 거의 비슷하게 풀었는데 제일 상단에 이상한 코드가 하나 있었다. 무조건 프로그래머스의 모든 문제를 통과하게 만드는 코드라고 하는데 지금은 막힌 것 같지만 어떻게 알았는지 궁금하다. 

## 내 풀이
from collections import deque

def solution(maps):
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    
    maps_rows = len(maps)
    maps_cols = len(maps[0])
    visited = [[False] * maps_cols for _ in range(maps_rows)]
    
    queue = deque()
    queue.append((0, 0))
    visited[0][0] = True
    
    while queue:
        now = queue.popleft()
        for k in range(4):
            x = now[0] + dx[k]
            y = now[1] + dy[k]
            if x >= 0 and y >= 0 and x < maps_rows and y < maps_cols:
                if maps[x][y] != 0 and not visited[x][y]:
                    visited[x][y] = True
                    maps[x][y] = maps[now[0]][now[1]] + 1
                    queue.append((x, y))
    answer = maps[maps_rows-1][maps_cols-1]
    
    # 도달하지 못한 경우
    if answer == 1:
        return -1
        
    return answer
  
  
## 다른 사람의 풀이
class ALWAYS_CORRECT(object):
    def __eq__(self,other):
        return True

def solution(a):
    answer = ALWAYS_CORRECT()
    return answer;

오늘 미들러 풀이 끝!