[백준] 1261 - 알고스팟 (JAVA)

1. 소요시간 : 15분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드 4
4. 문제 유형 : 그래프 이론, 그래프 탐색, 다익스트라, 0-1 너비우선탐색
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/1261
8. 푼 날짜 : 2023.04.10

1. 사용한 자료구조 & 알고리즘

다익스트라 알고리즘, bfs

2. 풀이과정

1. map[0][0] 은 과 map[n-1][m-1]은 항상 0이라는 가정이 있으니 그냥 바로 0개의 벽을 부순 좌표 0,0을 queue에 넣음.
2. 다른 좌표까지 가는 거리는 우선 INF 로 둠
3. 다음 좌표까지 갔는데 이전에 여기보다 벽을 덜 부순 경우가 있다면 갱신
4. 다음 좌표까지 벽을 더 부수면서 간다면 아예 다음 좌표로 가지 않음
   (다익스트라 알고리즘의 개념. )

3. 소스코드

import java.util.*;
import java.io.*;

public class Main{


	static StringBuilder sb=new StringBuilder();
	static int map[][];
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
	
		
		st=new StringTokenizer(br.readLine());

		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		map=new int[m][n];
		
		for(int i=0;i<m;i++) {
			String line=br.readLine();
			for(int j=0;j<n;j++) {
				map[i][j]=line.charAt(j)-'0';
			}
		}
		
		bfs();
		
		
	}
	public static void bfs() {
		int dist[][]=new int[map.length][map[0].length];
		for(int i=0;i<dist.length;i++)
			Arrays.fill(dist[i],Integer.MAX_VALUE);
		Queue<Integer[]> queue=new LinkedList<>();
		int dy[]= {0,0,-1,1};
		int dx[]= {-1,1,0,0};
		queue.add(new Integer[] {0,0,0});
		dist[0][0]=0;
		
		while(!queue.isEmpty()) {
			Integer temp[]=queue.poll();
			int nowY=temp[0];
			int nowX=temp[1];
			int broken=temp[2];
		//	System.out.println(123);
			for(int i=0;i<4;i++) {
				int nextY=nowY+dy[i];
				int nextX=nowX+dx[i];
				if(nextY<0||nextX<0||nextY>=map.length||nextX>=map[0].length)
					continue;
				if(map[nextY][nextX]==0) {
					if(dist[nextY][nextX]>broken) {
						dist[nextY][nextX]=broken;
						queue.add(new Integer[] {nextY,nextX,broken});
					}
				}
				else {
					if(dist[nextY][nextX]>broken+1) {
						dist[nextY][nextX]=broken+1;
						queue.add(new Integer[] {nextY,nextX,broken+1});
					}
				}
				
				
			}
			
			
		}
		
		
		System.out.println(dist[map.length-1][map[0].length-1]);
	}
}

4. 결과

5. 회고

다익스트라 알고리즘의 개념을 1번 더 상기한 문제다.
하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212