미로 탈출

2024. 7. 2. 15:04· 알고리즘/프로그래머스
728x90
 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr


BFS로 풀면 되는 문제.

 

BFS 탐색 함수를 따로 구현해서

시작지점 ~ 레버까지의 최단거리, 레버 ~ 도착지점까지의 최단거리를 각각 구한 후 더해주면 된다.

만약 2가지 최단거리 중 하나라도 None이 나오는 경우에는 도착이 불가능한 경우이므로 -1을 리턴해준다.

 

풀이 코드

from collections import deque

# BFS 돌리기
def bfs(maps, start_x, start_y, end_x, end_y, end_val):
    n = len(maps)
    m = len(maps[0])
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    
    visited = [[0] * m  for _ in range(n)]
    
    q = deque([(start_x, start_y)]) # 탐색 시작 노드 큐에 넣기
    visited[start_x][start_y] = 0 # 탐색 시작 노드 방문 처리
    
    while q:
        x, y = q.popleft()
        
        if maps[x][y] == end_val: # 큐에서 꺼낸 노드에서 탐색을 종료시켜야 하는 경우
            return visited[x][y]
        
        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 visited[nx][ny]:
                continue
            
            if maps[nx][ny] == 'X':
                continue
            # 'X'인 경우 제외하고는 모두 큐에 넣는다.
            else:
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx, ny))
            


def solution(maps):
    answer = 0
    
    start_x = 0
    start_y = 0
    end_x = 0
    end_y = 0
    lever_x = 0
    lever_y = 0
    
    n = len(maps)
    m = len(maps[0])
    
    # 시작 지점, 춝, 레버 저장
    for i in range(n):
        for j in range(m):
            if maps[i][j] == 'S':
                start_x = i
                start_y = j
            elif maps[i][j] == 'E':
                end_x = i
                end_y = j
            elif maps[i][j] == 'L':
                lever_x = i
                lever_y = j
                
    first = bfs(maps, start_x, start_y, lever_x, lever_y, 'L') # 시작 지점에서 레버까지의 최단 거리
    second = bfs(maps, lever_x, lever_y, end_x, end_y, 'E') # 레버에서 도착점까지의 최단 거리
    
    if first == None or second == None: # 둘 중 하나라도 None을 리턴한다면 이동할 수 없는 것
        answer = -1
    else:
        answer = first + second
    
    return answer

 

 

쉽게 풀 수 있던 BFS 문제였지만 오랜만에 풀어서 사소한 부분에서 미스가 났던 문제.

몇 번 수정하니 통과할 수 있었다.

728x90

'알고리즘 > 프로그래머스' 카테고리의 다른 글

리코쳇 로봇  (0) 2024.07.06
거리두기 확인하기  (0) 2024.07.03
행렬 테두리 회전하기  (0) 2024.07.01
괄호 변환  (0) 2024.06.28
[카카오 인턴] 수식 최대화  (0) 2024.06.27
'알고리즘/프로그래머스' 카테고리의 다른 글
  • 리코쳇 로봇
  • 거리두기 확인하기
  • 행렬 테두리 회전하기
  • 괄호 변환
happenundo
happenundo
happenundo
2023~ 개발블로그
happenundo
전체
오늘
어제
  • 분류 전체보기 (207)
    • TIL (3)
    • 알고리즘 (188)
      • 프로그래머스 (47)
      • 백준 (69)
      • 파이썬 문법 (11)
      • 이것이 코딩테스트다 (46)
      • 알고리즘 노트 (6)
      • SQL (8)
    • Spring (4)
      • Spring 입문 (2)
      • 개인 프로젝트 (1)
      • 인텔리제이 (1)
    • CS (8)
      • DB (2)
      • 네트워크 (1)
      • 그외 (5)
    • ~2022 (1)
    • etc (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 프로그래머스
  • 괄호변환
  • 구현
  • 파이썬
  • 백트래킹
  • 동적프로그래밍
  • BFS
  • 이진탐색
  • deepcopy
  • 플로이드워셜
  • DP
  • 다익스트라
  • dfs
  • 재귀
  • 우선순위큐
  • 큐
  • 이코테
  • BinarySearch
  • 알고리즘
  • 다이나믹프로그래밍
  • 최단거리
  • CS
  • sql
  • 이것이코딩테스트다
  • 정렬
  • distinct
  • 스택
  • 완전탐색
  • 백준
  • 그리디

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
happenundo
미로 탈출
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.