[DFS & BFS] 프로그래머스_게임 맵 최단거리 & 나동빈_미로탈출

들어가기 전에 알아야 할 것!

2차원 배열 크기 확인 방법

행 크기

maps = [[1,0,1,1,1],[1,0,1,0,1]]
print(len(maps))

출력값 : 2 (드래그)

열 크기

maps = [[1,0,1,1,1],[1,0,1,0,1]]
print(len(maps[0]))

출력값 : 5 (드래그)

return문에서 if-else문 이용하기

원래 방식

if answer == 1:
	return -1
else:
	return answer

한줄로 간결히 코딩하기

return -1 if answer == 1 else answer

---

게임맵 최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844?language=python3

프로그래머스

문제는 위 링크에서 확인해 주세요!

이 문제를 풀며 중요하게 생각한 아이디어는 다음과 같습니다!

1. 최단경로를 구하는 문제니 바로 BFS 생각해 내기

2. 상하좌우로 한 칸이라는 제약이 있다면 방향벡터 만들기!

방향벡터는 특별한 건 없고, 크기가 4인 두 1차원 리스트 dx와 dy를 생성해서 둘 다 인덱스가 0일 때는 상, 1일 때는 하, 2일 때는 좌, 3일 때는 우로 생각하면 됩니다. 

3. bfs 방식을 제대로 이해하고 조건에 따라 if문으로 나누어 생각하기

bfs는 큐에 탐색 노드를 삽입하며 방문 처리하고, 꺼내면서 인접 노드 중에서 방문하지 않는 노드를 모두 큐에 삽입하며 방문처리하는 방식인데요! 방문처리를 하지 않으면 무한 루프에 빠질 수 있기 때문에 방문처리를 꼭 해야 합니다.

 

아래 코드는 이 3가지 아이디어를 가지고 코딩한 결과물입니다!

from collections import deque

def solution(maps):
    answer = 0
    
    # 중요! 상하좌우로 움직이는 경우 dx, dy 정의하기
    # 상하좌우 #상:(-1,0), 하:(1,0), 좌:(0,-1), 우:(0,1)
    dx = [-1, 1, 0, 0]  # 행 이동
    dy = [0, 0, -1, 1]  # 열 이동
    
    def bfs(x,y):
        queue = deque()
        queue.append((x,y))  #현재 노드 추가(캐릭터가 서있는 칸) 
        # x,y 튜플을 queue에 넣고 이를 통해 상하좌우 확인할 것
        
        while queue: #큐가 빌 때까지
            x,y = queue.popleft()   #bfs : 현재 노드 pop하고 그 주변노드 탐색, 선입선출
            for i in range(4):
                # nx, ny는 현재노드에서 이동할 상하좌우 노드
                nx = x+dx[i]
                ny = y+dy[i]
                
                # 맵을 벗어나는 경우
                # nx, ny는 0부터 시작
                if (nx < 0 or nx >= len(maps) or ny < 0 or ny >= len(maps[0])):
                    continue
                # 벽인 경우
                if (maps[nx][ny]==0):
                    continue
                # 처음 가는 길인 경우
                if (maps[nx][ny]==1):
                    # 직전노드 위치에서의 최단 거리 값에 1을 더한 값은 넣어줌
                    maps[nx][ny] = maps[x][y] + 1
                    queue.append((nx,ny))   #bfs : x,y 주변노드 추가 #재귀
        return maps[len(maps)-1][len(maps[0])-1]  #가장 오른쪽 아래까지의 최단 거리 반환
    
    answer = bfs(0,0)
    
    return -1 if answer == 1 else answer

여기서 while queue:를 통해 큐가 비어있지 않다면 반복하고, 큐가 비어있다면 while문이 종료되는 이유가 궁금하다는 친구의 피드백을 받았는데요!
왜냐하면, 큐를 포함한 리스트, 딕셔너리, Set, 문자열과 같은 자료형 모두 비어있을 때 False를 리턴하기 때문입니다!

from collections import deque
queue = deque()
if queue:
    print("큐는 비어있지 않습니다.")
else:
    print("큐는 비어있습니다.")

False를 리턴하는지 확인하는 방법은 아래와 같이 bool() 함수를 사용하면 됩니다!

from collections import deque
queue = deque()
print(bool(queue))  # 출력 결과는 False

<자가 피드백>

다른 사람 코드랑 비교해 보며 if 조건문에 () 쓰는 습관을 고쳐야겠다고 생각했다. 괜히 시간만 더 투자하고 만약 제대로 괄호 안 닫으면 오류만 나기 때문에 ()를 쓰지 않아야겠다고 생각했다.

bfs, dfs가 이론으로는 너무 쉬운데 막상 코드에 적용하기는 좀 어려웠는데 이번에 문제를 풀며 bfs는 확실히 이해한 듯하다! dfs도 더 풀어보면 쉽게 코딩할 수 있을 거 같다!

---

프로그래머스 게임 맵 최단거리 문제는 나동빈 미로탈출 코드랑 비교해 가며 푸니 확실히 이해가 갔는데요!

아래에 코드랑 영상 링크 남겨둘게요! 미로탈출 문제는 51:18초부터 나옵니다.

from collections import deque

n,m = map(int, input().split())
maze = [list(map(int, input())) for _ in range(n)] 
#공백구분없이 입력받아 split() 사용 안함

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

def bfs(x, y):
  queue = deque()
  queue.append((x,y))

  while queue:
    x,y = queue.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      # 미로 공간 벗어난 경우
      if nx < 0 or nx >= n or ny < 0 or ny >= m:
        continue
      # 벽인 경우
      if maze[nx][ny] == 0:
        continue
      # 해당 노드를 처음 방문할 때만 최단 거리 기록
      if maze[nx][ny] == 1:
        maze[nx][ny] = maze[x][y] + 1
        queue.append((nx, ny))
  return maze[n-1][m-1]

print(bfs(0,0))

(분명히 맞은 거 같은데 답이 이상하다면 들여 쓰기 확인하기...ㅎ)

 

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4