[BAEKJOON]14940 쉬운 최단거리

문제 요약

• 알고리즘 분류: bfs, 구현, 시물레이션
• 난이도:Silver1
• 문제내용:
  • 가로, 세로 크기가 n, m인 지도가 있다
  • 2는 시작점 1은 갈수 있는 길, 0은 갈수 없는 곳
  • 시작점 부터 각 지점 목적지를 출력해라 그리고 목적지 도달 하지 못하는 곳은 -1로 출력해라
• 사이트: https://www.acmicpc.net/problem/14940

14940번: 쉬운 최단거리

문제풀이

 이번 문제는 BFS 탐색 문제이다. BFS 탐색 알고리즘에 관한 자세한 설명은 여기에서 확인 해보면 알 수 있다.

 기존 BFS는 각 노드간의 탐색인데 이번에는 2차원 배열로 응용한 BFS 탐색이다. 노드 대신 2차원 배열로 변경 된것만 생각하면 된다.

 

문제 접근 방법

 이번 문제에서 크게 구현 해야 할 것은 크게 3가지로 보면된다.

 1. 시작점 찾기

 2. bfs 구현

 3. 탐색 못하는 영역 처리

 이번 문제의 핵심는 BFS + 시물레이션 2개를 구현 해야 한다.  구현 방법은 간단하다. 아래 그림 처럼 bfs 탐색 하면 현재 위치에 + 1만 더해 주면 된다. 하지만 bfs 탐색 할때 기존 시뮬레이션에서 갈수 없는 길에서 시작 점에서 탐색을 하면 안된다는 조건만 추가만 해주면된다.

그리고 마지막으로 전체 2차원 배열에서 갈 수 있는 길인데 탐색 못한 영역은 -1로 바꾸는 작업만 하면 끝이다. 

 

 

시작점 찾는 코드

문제에서 (0, 0)부터 시작하는 것이 아니라서 시작 위치를 먼저 찾아야 한다.

Python

def findStartLocation():
    for i in range(n):
        for j in range(m):
            if boards[i][j] == 2:
                return (i, j)

Java

int x = 0;
int y = 0;

// 시작 위치 찾기
for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        if (boards[i][j] == 2){
            x = i;
            y = j;
            break;
        }
    }
}

 

BFS

Python

파이썬 지원하는 모듈에서는 queue가 없어서 deque(데크)를 사용 해서 queue로 구현 해야한다. queue는 pip에 따로 install을 받으면되지만 실제 코딩테스트에서는 불가능 하기 때문에 deque로 사용 해야한다.

queue = deque()
queue.append(findStartLocation())

distances = [[0] * m for _ in range(n)]

while queue:
    x, y = queue.popleft()

    for k in range(4):
        fx, fy = x + dx[k], y + dy[k]
        if (0 <= fx < n and 0 <= fy < m) and (boards[fx][fy] != 2 and boards[fx][fy] == 1 and distances[fx][fy] == 0):
            distances[fx][fy] = distances[x][y] + 1
            queue.append((fx, fy))

return notFindLoad(distances)

Java

자바에서는 Queue라는 모듈을 제공하기 때문에 queue를 따로 구현하지 말고 Queue 모듈을 사용하면된다.

Queue<int []> queue = new LinkedList<>();
queue.add(new int[] {x, y});
int[] location;
int fx, fy;

//bfs 탐색 시작
while (queue.size() > 0){
    location = queue.poll();
    x = location[0];
    y = location[1];

    for(int k = 0; k < 4; k++){
        fx = x + dx[k];
        fy = y + dy[k];
        if((fx >= 0 && fx < n && fy >= 0 && fy < m) && boards[fx][fy] == 1 && boards[fx][fy] != 2 && distances[fx][fy] == 0){
            distances[fx][fy] = distances[x][y] + 1;
            queue.add(new int[] {fx, fy});
        }
    }

}

 

탐색 못 한 영역 처리

 문제에서 마지막으로 처리 해야 하는것이 길은 있는데 탐색 못하는 곳은 -1로 표기 하라고 한다. 예제 케이스에서는 없지만 이 부분까지 처리를 해야 통과가 된다.

Python

def notFindLoad(arrays):
    for i in range(n):
        for j in range(m):
            if (boards[i][j] == 1 and arrays[i][j] == 0):
                arrays[i][j] = -1

    return arrays

Java

public static int[][] notFindLoad(int[][] arrays){

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if (arrays[i][j] == 0 && boards[i][j] == 1){
                arrays[i][j] = -1;
            }
        }
    }
    return arrays;
}

 

Code

python

from collections import deque
import sys

input = sys.stdin.readline

# 시작 위치 찾기
def findStartLocation():
    for i in range(n):
        for j in range(m):
            if boards[i][j] == 2:
                return (i, j)

def notFindLoad(arrays):
    for i in range(n):
        for j in range(m):
            if (boards[i][j] == 1 and arrays[i][j] == 0):
                arrays[i][j] = -1

    return arrays

def bfs():
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    queue = deque()
    queue.append(findStartLocation())

    distances = [[0] * m for _ in range(n)]

    while queue:
        x, y = queue.popleft()

        for k in range(4):
            fx, fy = x + dx[k], y + dy[k]
            if (0 <= fx < n and 0 <= fy < m) and (boards[fx][fy] != 2 and boards[fx][fy] == 1 and distances[fx][fy] == 0):
                distances[fx][fy] = distances[x][y] + 1
                queue.append((fx, fy))

    return notFindLoad(distances)


n, m = map(int, input().split())
boards = [list(map(int, input().split())) for _ in range(n)]

for array in bfs():
    print(' '.join(map(str, array)))

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int n, m;
	static int[][] boards;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		boards = new int[n][m];

		for(int i = 0; i < n; i++){
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < m; j++){
				boards[i][j]  = Integer.parseInt(st.nextToken());
			}
		}

		int[][] distances = bfs();
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				sb.append(distances[i][j]).append(" ");
			}
			sb.append("\n");
		}

		System.out.println(sb.toString());

	}

	public static int[][] bfs(){

		int[] dx = {0, 0, -1, 1};
		int[] dy = {-1, 1, 0, 0};

		int[][] distances = new int[n][m];
		Arrays.stream(distances).forEach(distance -> Arrays.fill(distance, 0));


		int x = 0;
		int y = 0;

		// 시작 위치 찾기
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if (boards[i][j] == 2){
					x = i;
					y = j;
					break;
				}
			}
		}

		Queue<int []> queue = new LinkedList<>();
		queue.add(new int[] {x, y});
		int[] location;
		int fx, fy;

		//bfs 탐색 시작
		while (queue.size() > 0){
			location = queue.poll();
			x = location[0];
			y = location[1];

			for(int k = 0; k < 4; k++){
				fx = x + dx[k];
				fy = y + dy[k];
				if((fx >= 0 && fx < n && fy >= 0 && fy < m) && boards[fx][fy] == 1 && boards[fx][fy] != 2 && distances[fx][fy] == 0){
					distances[fx][fy] = distances[x][y] + 1;
					queue.add(new int[] {fx, fy});
				}
			}

		}

		return notFindLoad(distances);
	}

	/*
	* 도달 할 수 없는 땅 찾기
	 */
	public static int[][] notFindLoad(int[][] arrays){

		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if (arrays[i][j] == 0 && boards[i][j] == 1){
					arrays[i][j] = -1;
				}
			}
		}
		return arrays;
	}

}