[Baekjoon] 2178_미로 탐색

Silver I

문제(출처: https://www.acmicpc.net/problem/2178)

---

<미로 탐색>

문제 

 

N×M크기의 배열로 표현되는 미로가 있다.

 

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

 

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

 

입력

 

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

 

 

출력 

 

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

 

문제 풀이

   - my solution (Python)

import sys
from collections import deque

def maze(graph, start, depth):
    dx=[-1,1,0,0] # 상하좌우
    dy=[0,0,-1,1]

    visited = [[0] * len(graph[0]) for i in range(len(graph))] # 방문 여부
    visited[start[0]][start[1]]=1
    queue=deque([start])

    while queue:
        temp=queue.popleft()
        for i in range(4):
            x=temp[0]+dx[i]
            y=temp[1]+dy[i]
            if  x>=0 and x<len(graph) and y>=0 and y<len(graph[0]): # 미로 범위 안이라면
                if graph[x][y]==1 and visited[x][y]==0: # 이동할 수 있으며 아직 방문하지 않았다면
                    queue.append([x,y])
                    visited[x][y]=1
                    depth[x][y]=depth[temp[0]][temp[1]]+1
if __name__=='__main__':
    n,m=map(int, sys.stdin.readline().split())

    graph=[]
    for i in range(n):
        graph.append(list(map(int, sys.stdin.readline().strip())))

    depth = [[0] * m for i in range(n)]
    start=[0,0] # 출발

    maze(graph, start, depth)

    print(depth[n-1][m-1]+1)

한 번에 통과하고 싶어서 원래 list 쓰던 거 deque 썼다!

 

 

- my solution (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class _2178_미로탐색 {
	
	static void maze(int graph[][], int start[], int depth[][]) {
		int dx[]= {-1,1,0,0}; //상하좌우
		int dy[]= {0,0,-1,1};
		
		int visited[][]=new int[graph.length][graph[0].length]; // 방문 여부
		visited[start[0]][start[1]]=1;
		
		Queue<int []> queue=new LinkedList<>();
		queue.add(start);
		
		while(queue.size()!=0) {
			int[] temp=queue.poll();
			for(int i=0; i<4; i++) {
				int x=temp[0]+dx[i];
				int y=temp[1]+dy[i];
				if(x>=0&& x<graph.length && y>=0 && y<graph[0].length) { //미로 범위 안이라면
					if(graph[x][y]==1 && visited[x][y]==0) { // 이동할 수 있으며 아직 방문하지 않았다면
						queue.add(new int[] {x,y});
						visited[x][y]=1;
						depth[x][y]=depth[temp[0]][temp[1]]+1;
					}
				}
			}
		}
	}

	public static void main(String[] args) throws IOException{
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		
		String str=bf.readLine();
		int n=Integer.parseInt(str.split(" ")[0]);
		int m=Integer.parseInt(str.split(" ")[1]);
		
		int graph[][]=new int[n][m];
		for(int i=0; i<n; i++) {
			str=bf.readLine();
			for(int j=0; j<m; j++) {
				graph[i][j]=Integer.parseInt(str.split("")[j]);
			}
		}
		
		int depth[][]=new int[n][m];
		int start[]= {0,0}; //출발
		
		maze(graph, start, depth);
		
		System.out.println(depth[n-1][m-1]+1);
	}

}

 

(0,0)부터 시작해서 상하좌우를 확인하여 갈 수 있는 길이면 계속해서 나아가며 depth를 저장해주기만 하면 쉽게 풀 수 있는 문제였다.

• maze
  : dx, dy = 상하좌우 탐색
  : visited = 방문 여부
  : queue가 빌 때까지 반복 -> 제일 처음 값을 pop -> 상하좌우 확인하여 미로 범위 안이며 이동할 수 있고, 아직 방문하지 않았다면 queue에 추가 및 방문 check, depth 저장
  (이동할 위치의 depth = 현재 위치의 depth +1)
• main
  : n, m 입력
  : 미로 입력
  : depth = 지나야 하는 칸 수 저장
  : 함수 호출
  : answer = 시작 위치와 도착 위치도 포함 이므로 depth [n-1][m-1] +1 

 

---

생각🤔

 

보자마자 후다닥 코드 구현해서 성공 -!

한 번에 통과해서 뿌듯-!

JAVA 빨리.. 익숙해져야겠다. 까먹은 내용이 너무 많아서...

 

 

---