[백준, Java] 17129번, 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유(BFS)

문제 링크

17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. n × m 격자 모양의 섬이 존재합니다.

2. 섬에는 청국장(3), 스시(4), 맥앤치즈(5), 딱따구리(2)가 존재합니다.

3. 장애물(1)은 지나갈 수 없으며, 딱다구리는 상하좌우로 움직일 수 있습니다.

4. 딱다구리가 음식에 도착할 수 있는 최단 거리를 결과로 출력합니다.

5. 음식에 도착할 수 있으면 "TAK", 없으면 "NIE"을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. BFS을 통해서 딱다구리가 음식에 도착하는 최단 거리를 탐색합니다.

 

3. 탐색한 최단 거리를 결과로 출력합니다.

 

BFS(딱다구리 음식 최단 거리 구하기)

 

BFS을 통해서 딱다구리 시작 위치를 기준으로 가장 가까운 음식을 찾는 과정을 진행합니다.

 

딱다구리는 상하좌우로 움직일 수 있기 때문에

 

y변경 값 : { -1, 1, 0, 0 }

 

x변경 값 : { 0, 0, -1, 1 }

 

※예제 입력 과정을 살펴보시면 이해하시기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

n : 3

 

m : 3

 

정보섬

 

2	0	0
0	0	3
0	4	5

 

2. BFS을 통해서 딱다구리가 음식에 도착하는 최단 거리를 탐색합니다.

 

딱다구리 시작 위치(0,0)

 

시작위치를 기준으로 BFS 탐색 진행

 

거리가 1일 때

 

2	0	0
0	0	3
0	4	5

 

거리가 2일 때

 

2	0	0
0	0	3
0	4	5

 

거리가 3일 때

 

2	0	0
0	0	3
0	4	5

청국장(3), 스시(4) 첫 방문으로 최단 거리 구하기 완료!

 

3. 탐색한 최단 거리를 결과로 출력합니다.

 

최단 거리 : 3

 

3을 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여  섬의 크기 정보를 띄어쓰기 기준 저장합니다.
• search함수를 딱다구리 기준 음식을 방문하는 최단 거리를 탐색합니다.
• 탐색을 통해 얻은 최단 거리를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search함수는 BFS을 통해서 딱다구리가 음식을 방문하는 최단 거리를 구합니다.
• inSpace함수는 이동하려는 공간이 정보섬에 존재하는지 확인합니다.

결과코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
    //BFS에 사용할 클래스
    static class Pair{
        int r, c, moveCnt;
        Pair(int r, int c, int moveCnt){
            this.r = r;
            this.c = c;
            this.moveCnt = moveCnt;
        }
    }
    //상하좌우 r, c 변경값
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] island = new int[n][m];
        int start = 0;
        int end = 0;
        //입력값 저장
        for(int i=0;i<n;i++){
            String input = br.readLine();
            for(int j=0;j<m;j++){
                island[i][j] = Character.getNumericValue(input.charAt(j));
                //딱다구리 시작 위치 저장
                if(island[i][j] == 2){
                    start = i;
                    end = j;
                }
            }
        }
        //BFS을 통해 음식 최단 거리 구하기
        int result = search(island, start, end, n, m);
        //도착할 수 있는 음식이 없을 때
        if(result == -1){
            bw.write("NIE");
        }else{	//도착할 수 있는 음식이 있을 때
            bw.write("TAK\n");
            bw.write(Integer.toString(result));
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS을 통해서 딱다구리가 음식에 방문하는 최단 거리 구하는 함수
    static int search(int[][] island, int start, int end, int n, int m){
        //BFS에 사용할 Queue
        Queue<Pair> q = new LinkedList<>();
        boolean[][] visited = new boolean[n][m];
        //시작 위치 저장
        visited[start][end] = true;
        q.offer(new Pair(start, end, 0));
        //BFS 탐색
        while(!q.isEmpty()){
            Pair cur = q.poll();
            //청국장(3), 스시(4), 맥앤치즈(5)에 방문했을 때, 최단 거리
            if(island[cur.r][cur.c] == 3 || island[cur.r][cur.c] == 4 || island[cur.r][cur.c] == 5){
                return cur.moveCnt;
            }
            //상하좌우 인접한 공간 탐색
            for(int i=0;i<4;i++){
                int tempR = cur.r + dr[i];
                int tempC = cur.c + dc[i];
                if(inSpace(tempR, tempC, n, m) && !visited[tempR][tempC] && island[tempR][tempC] != 1){
                    visited[tempR][tempC] = true;
                    q.offer(new Pair(tempR, tempC, cur.moveCnt+1));
                }
            }
        }
        //도달할 수 있는 음식이 없을 때
        return -1;
    }
    //이동하려는 칸이 정보섬에 존재하는지 확인하는 함수
    static boolean inSpace(int r, int c, int n, int m){
        if(r >= 0 & c >= 0 && r < n && c < m){
            return true;
        }
        return false;
    }
}