[Baekjoon] 17129_윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유

Silver I

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

---

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

 

문제 풀이

 

bfs를 활용하며 가장 빨리 도착할 수 있는 음식까지의 최단 거리를 구하였다.

 

 

 - my solution (Java)

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

public class _17129_ {
	static int n,m, arr[][], result;
	static boolean visited[][];
	static int dx[]= {-1,1,0,0};
	static int dy[]= {0,0,-1,1};

	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		n=Integer.parseInt(st.nextToken());
		m=Integer.parseInt(st.nextToken());
		
		arr=new int[n][m];
		visited=new boolean[n][m];
		result=-1;
		
		int x=-1, y=-1;
		for(int i=0; i<n; i++) { // input
			String str=bf.readLine();
			for(int j=0; j<m; j++) {
				arr[i][j]=str.charAt(j)-'0';
				if(arr[i][j]==1) visited[i][j]=true;
				if(arr[i][j]==2) { // 윌리암슨수액빨이딱따구리 위치
					x=i;
					y=j;
				}
			}
		}
		search(x,y);
		if(result>-1) {
			System.out.println("TAK");
			System.out.println(result);
		}else System.out.println("NIE");
	}

	private static void search(int x, int y) {
		Queue<int[]>queue=new LinkedList<>();
		queue.add(new int[] {x,y,0});
		visited[x][y]=true;
		
		while(!queue.isEmpty()) {
			int temp[]=queue.poll();
			for(int i=0; i<4; i++) {
				int num1=temp[0]+dx[i];
				int num2=temp[1]+dy[i];
				if(num1>=0 && num1<n && num2>=0 && num2<m && !visited[num1][num2]) {
					visited[num1][num2]=true;
					if(arr[num1][num2]==3 || arr[num1][num2]==4 || arr[num1][num2]==5) {
						result=temp[2]+1;
						break;
					}
					queue.add(new int[] {num1, num2, temp[2]+1});
				}
			}
			if(result>-1) break;
		}
	}
}

 

Main

- 정보섬의 크기 n과 m 입력

- 정보섬 정보를 입력받으며 장애물로 막힌 부분은 이동할 수 없으므로 방문 표시를 하고, 시작 위치인 윌리암슨수액빨리딱따구리 위치를 저장해 둔다.

- search 함수 호출

- 음식을 먹을 수 있으면 TAK과 최단 거리 출력, 음식을 먹을 수 없으면 NIE 출력

 

Search

- queue에 [x좌표, y좌표, 거리]를 넣어준다.

- queue가 빌 때까지 반복하며 상하좌우를 탐색하여 정보섬 내부이며 아직 방문하지 않은 곳이면 방문 표시 및 queue에 넣어준다. 만약 음식에 도달했으면 reuslt에 값을 넣어준 후 바로 종료해 준다.

---

생각🤔

 

---