백준 1261번(JAVA)

다익스트라를 응용하는 문제이다. BFS와 다익스트라를 모두 다룰줄 안다면 손쉽게 풀 수 있다.

기본 다익스트라를 모를 경우 아래 링크에서 참고하도록 하자.

2021.04.24 - [백준 문제풀이(JAVA)/그래프] - 백준 1916번(JAVA)

백준 1916번(JAVA)

일반 다익스트라와 다른점을 꼽자면 굳이 연결정보를 안알려준다는 것이다.

나는 단순하게 생각했다. 현재정점의 위,아래,오른쪽,왼쪽은 모두 연결되어있으며 만약 벽이 있다면 가중치가 1,벽이 없다면 가중치가 0.물론 위,아래,오른쪽,왼쪽은 주어진 범위안에 있는지 확인해야한다.

위에만 생각해냈다면 문제는 끝이다. 나머지는 일반 다익스트라와 똑같이 실시하면 된다.

소스코드

import java.util.*;
import java.io.*;
class Node implements Comparable<Node>
{
	int y;
	int x;
	int weight;
	public Node(int y,int x,int weight)
	{
		this.y=y;
		this.x=x;
		this.weight=weight;
	}
	@Override
	public int compareTo(Node o)
	{
		return weight-o.weight;
	}//우선순위 큐에 넣을때 가중치가 가장 작은게 큰 우선순위를 갖도록 구현
}
public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String[] s=br.readLine().split(" ");
		int M=Integer.parseInt(s[0]);
		int N=Integer.parseInt(s[1]);
		int[][] map=new int[N][M];//벽이 있는지없는지를 나타내는 map배열
		boolean[][] visited=new boolean[N][M];//방문했는지 확인하는 배열
		for(int i=0;i<N;i++)
		{
			s=br.readLine().split("");
			for(int j=0;j<M;j++)
			{
				map[i][j]=Integer.parseInt(s[j]);
			}
		}
		int[] dx= {0,1,0,-1};
		int[] dy= {1,0,-1,0};//4방향을 모두 확인하기 위한 배열
		int[][] result=new int[N][M];//출발점에서 해당지점까지 벽을 부셔야하는 갯수값,일반 다익스트라에서의 dis랑 같다
		for(int i=0;i<N;i++)
		{
			for(int j=0;j<M;j++)
			{
				result[i][j]=Integer.MAX_VALUE;
			}
		}//다익스트라에서 하듯이 최대값으로 모두 초기화
		result[0][0]=0;//시작점인 0,0만 0으로 초기화
		PriorityQueue<Node> q=new PriorityQueue<Node>();
		q.add(new Node(0,0,0));//0,0에서 시작
		while(!q.isEmpty())
		{
			Node temp=q.poll();
			int y=temp.y;
			int x=temp.x;
			int weight=temp.weight;
			if(!visited[y][x])
			{
				for(int i=0;i<4;i++)
				{
					int ny=y+dy[i];
					int nx=x+dx[i];
					if(ny>=0&&ny<N&&nx>=0&&nx<M)//가고자 하는 방향이 map의 범위를 벗어나는지 확인
					{
						if(!visited[ny][nx]&&map[ny][nx]==1)//방문된적없고 벽이 있다면
						{
							if(result[ny][nx]>result[y][x]+1)//result에 1더해야한다.
							{
								result[ny][nx]=result[y][x]+1;
								q.add(new Node(ny,nx,result[ny][nx]));
							}
						}
						else if(!visited[ny][nx]&&map[ny][nx]==0)//방문된적없고 벽이 없다면
						{
							if(result[ny][nx]>result[y][x])//result 그대로 간다. 더할 필요없다.
							{
								result[ny][nx]=result[y][x];
								q.add(new Node(ny,nx,result[ny][nx]));
							}
						}
					}
				}
			}
			visited[y][x]=true;//해당 정점과 연결된걸 모두 확인했기에 방문처리해준다.
		}
		System.out.println(result[N-1][M-1]);
	}
}

댓글과 지적은 언제든지 환영입니다~!

글이 마음에 들었다면 왼쪽 이미지를 눌러 후원 부탁드립니다~! ><