99클럽 코테 스터디 6일차 TIL + 프로그래머스 게임 맵 최단거리

 

 

 

전형적인 BFS 문제이다!

맵이 나오면 dy, dx를 설정하고 내가 가는 방향에 대한 선택지를 제공한다고 생각하면 좋다.

근데 이 문제가 나에게 멘붕을 준 이유는...

 

맵이 5X5라고 나와있어서 모든 입력 맵이 5X5라고 생각하고 하드코딩 했기 때문...!

 

일단 기본적인 문제 풀이 과정을 설명하자면

1. dx, dy global로 설정

2. BFS 함수를 새로 두고 

1. 그 안에서 먼저 시작점을 queue에 push
2. while 문을 돌면서 queue가 모두  빌때까지 진행
   1. 먼저 queue에서 pop -> 한칸 이동하는 것!
   2. for 문으로 4번 돌면서 상, 하 , 좌, 우 에 대해 유효한 길을 찾는다 ( 여기서는 길이 1이라고 되어 있는 걸 찾기)
   3. 길을 찾으면 그 길에 대한 x,y 값을 queue에 push
   4. 따로 cnt를 둬도 가능하지만 난 map에 update하면서 경로를 기억하도록 했다.

이걸 코드로 짜면 아래의 코드가 된다.

from collections import deque

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

def BFS(maps, x, y):
	# 매번 배열 크기 측정하기!
    size_x = len(maps[0])
    size_y = len(maps)
    
    queue = deque()
    queue.append((y,x))
    
    while queue:
        
        y, x = queue.popleft()
        
        # 상,하,좌,우 탐색
        for i in range(4):
            nx_y = y + dy[i]
            nx_x = x + dx[i]
            
            # index다 보니 반드시 확인해야할 부분
            if nx_y < 0 or nx_x < 0 or nx_y >= size_y or nx_x >= size_x:
                continue
            
            if maps[nx_y][nx_x] == 0:
                continue
            if maps[nx_y][nx_x] == 1:
                
                maps[nx_y][nx_x] = maps[y][x] + 1
                queue.append((nx_y, nx_x))
    
    return maps[size_y-1][size_x-1]
    
def solution(maps):
    answer = BFS(maps,0,0)
    
    # 경로 탐색에 실패한 경우
    if answer == 1:
        answer = -1
        
    return answer

 

 

결과는 ....!!!

 

성공이다!!!

근데 여기 정확성과 효율성 점수는 뭐지? 아! 이거 합쳐서 100점이라는 거구나!!🤩

 

괜히 쓸데없이 5로 가정하고 코드를 짜서 이상한곳에서 디버깅하느라 시간을 버렸다ㅜㅜ