프로그래머스_미로탈출_Day1

 

오랜만에 다시 알고리즘 풀이를 시작하려 한다. 
최근 가까운 지인을 통해 알고리즘 말고 다른 간단한 챌린지를 시작했는데, 챌린지 형식으로 진행하다 보니 열심히 빠짐없이 한 달 동안 완수할 수 있었던 것 같다. 

혼자 하다 보니 금세 또 보여지는 면이 없어서 실천이 어려울 수도 있지만, 같은 방식으로 스스로 챌린지를 진행하여 매일 한 문제씩 알고리즘을 풀고 블로그에 포스팅을 남기는 도전을 해보고자 한다. 

메인 언어인 자바를 비롯하여 가능하다면 파이썬까지 풀이를 두 가지로 하여 파이썬 복습 겸 챌린지를 시작해 보겠다. 

오늘 풀이해 볼 문제는 프로그래머스 level 2로 배정된 너비 우선 탐색 문제이다.

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

프로그래머스

 

BFS 알고리즘을 알고 있다면 간단한 로직으로 해결할 수 있는 문제이다.  

이 문제를 통해서 체크해야 할 핵심 조건은 아래와 같다. 

• 벽을 제외한 모든 정점을 지날 수 있다. 
• 미로가 정사각형이 아닌 직사각형이다. 
• 시작점 ~ 레버의 최단 거리 + 레버 ~ 출구의 최단거리를 구해야 한다. -> 총 2번의 BFS 탐색을 해야 한다.
• 전자는 경로가 있는데 후자는 경로가 없거나, 반대로 전자가 경로가 없는데 후자는 경로가 있는 경우는 -1을 리턴한다

 

자세한 설명은 코드속의 주석에서 달도록 하겠다.

JAVA 풀이

import java.util.*;
class Solution {
    static String  [][] MIRO;
    static boolean [][] checked;
    //                  상 하  좌  우
    static int []dx = {-1, 1,  0, 0};
    static int []dy = { 0, 0, -1, 1};
    static point start; 
    static point lever; 
    
    Queue<point> tunnel;
    
    public int solution(String[] maps) {
        MIRO = new String[maps.length][maps[0].length()];
        for(int i=0; i<maps.length; i++){
            String [] tmp = maps[i].split("");
            for(int j=0; j<tmp.length; j++){
                MIRO[i][j] = tmp[j];
                
                if(tmp[j].equals("S")){
                    start = new point(i, j, 0);
                }else if(tmp[j].equals("L")){
                    lever = new point(i, j, 0);
                }
            }
        }
        
        int time1 = BFS(start, "L");
        if(time1 == -1) return time1;
        int time2 = BFS(lever, "E");
        if(time2 == -1) return time2;
        
        return time1 + time2;
    }
    
    public int BFS(point start, String target) {
        checked = new boolean[MIRO.length][MIRO[0].length];
        tunnel = new LinkedList<>();
        tunnel.add(start);
        
        while(!tunnel.isEmpty()) {
            point now = tunnel.poll();
            checked[now.x][now.y] = true; 
            
            if(MIRO[now.x][now.y].equals(target)) return now.time; 
            
            for(int i=0; i<4; i++) {
                int nextX = now.x + dx[i];
                int nextY = now.y + dy[i];
                
                if(nextX >=0 && nextY >=0 && nextX <MIRO.length && nextY < MIRO[0].length && !checked[nextX][nextY]) {
                    if(!MIRO[nextX][nextY].equals("X")) {
                        checked[nextX][nextY] = true; 
                        tunnel.add(new point(nextX, nextY, now.time+1));    
                    }
                    
                }
                
            }
            
            
        }
        return -1;
    }
}
class point{
    int x;
    int y;
    int time;
     public point(int x, int y, int time) {
         this.x = x;
         this.y = y;
         this.time = time;
     }
}
/*
    너비 우선 탐색 방법을 사용해서 출구로 가는 최단거리 찾기. 
    단, 출구에 도착하기 전에 반드시 레버를 거쳐 가야 한다.
    출발 지점에서 레버로 가는 최단경로(=시간) + 레버에서 출구로 가는 최단 경로
*/

Python 풀이 

from collections import deque #collections 모듈에서 제공하는 deque 임포트

def bfs (start, end, maps) -> int:
    # 탐색 방향 (시작지점에서 상하좌우 4방면을 탐색할 것이다.)
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    row = len(maps) # 미로의 세로 = 행 수
    col = len(maps[0]) #미로의 세로 = 열 수
    visited = [[False]*col for _ in range(row)] # 방문 체크 배열 -> row행 col열의 2차원 리스트를 False로 초기화
    que = deque() # 빈 큐 생성
    
    # 출발지점을 찾기 위한 상태값
    flag = False
    
    # 초기화 : 출발지점을 찾으면 바로 큐에 넣고 flag값을 사용해 반복문을 탈출하여 바로 bfs를 시작한다.
    for i in range(row):
        for j in range(col):
            if maps[i][j] == start:
                que.append((i,j,0))
                visited[i][j] = True
                flag = True; break
            if flag: break
    queue = deque(start)
    
    # 너비 우선 탐색 시작
    while que:
        x, y, cost = que.popleft()
        
        # 목적지에 도착했다면 현재 cost값 반환
        if maps[x][y] == end:
            return cost
        
        # 현재 위치에서 4방면을 탐색
        for i in range(4):  
            nx = x + dx[i]
            ny = y + dy[i]
            
            # 배열의 범위를 벗어나지 않는 통로 중에서 아직 방문하지 않은 통로만 큐에 추가
            if 0<= nx < row and 0<= ny <col and maps[nx][ny] !='X':
                if not visited[nx][ny]:	# 아직 방문하지 않는 통로라면
                    que.append((nx, ny, cost+1))
                    visited[nx][ny] = True
    
    return -1

def solution(maps):
    path1 = bfs('S', 'L', maps) # 시작지점 ~ 레버의 최단 거리 
    path2 = bfs('L', 'E', maps) # 레버 ~ 출구의 최단 거리
    
    if(path1 == -1 or path2 == -1): # 두 경로 중 하나라도 찾을 수 없다면 -1 
        return -1
    
    return path1 + path2

 

까먹은 파이썬 자료구조 상기시키기 

리스트 (list)
- 대괄호('[]') 사용
- my_list = [1, 2, 3, 4, 5]
- my_list = [] #빈 괄호 생성 
- my_list.append(1)
-- append()를 사용하여 요소를 추가할 수 있고, 한 번의 한 가지 형태의 값만 넣을 수 있다. 
-- 데이터는 정수, 셋, 튜플, 리스트 등 다양하게 넣을 수 있다. 
- 순서가 있고 원소에 대한 인덱스가 존재한다. 

셋 (set)
- 중괄호 사용 ('{}')
- my_set = {1, 2, 3, 4, 5}
- my_set = set() # 빈 셋을 만드는 방법
- 중복을 허용하지 않고, 순서가 없는 집합
- 인덱스로 접근할 수 없음

사전 (dictionary) 
- 중괄호 사용 ('{}')
- 각 항목은 콜론으로 구분된 키와 값의 쌍으로 이루어 짐. map 구조 
- my_dict = {'a' : 1, 'b' : 2, 'c' : 3}

튜플 (tuple) 
- 소괄호 사용 ('()')
- 변경 불가능한 시퀀스 자료형으로 여러 값을 그룹화할 때 사용한다. 
- 각 요소는 쉼표로 구분
- 인덱스로 접근할 수 있다. 
- 값을 변경할 수 없기 때문에 값을 수정하고 싶다면, + 연산자를 사용해 새로운 튜플을 만들어야 한다. 
-- my_tuple = ()
-- my_tuple = my_tuple + (1,)
-- my_tuple = my_tuple + (2,)
-- 이제 my_tuple의 값은 (1,2)이다.