백준 14442번(JAVA)

반응형

벽 부수고 이동하기2 문제이다.

벽 부수고 이동하기1문제랑 매우 유사하기 때문에 같이보면 좋을듯 하다.

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

문제풀이는 간단하다.

객체를 생성할줄만 알면 문제는 매우 쉬워진다.

객체에는 좌표를 나타내는 x,y 그리고 몇칸째이동중인지를 나타내는 count 마지막으로 벽을 몇개를 부쉈는지를 나타내는 crash변수를 만들어낸다.

또한 BFS에서 필수인 방문체크 배열은 visited[i][j][k]로 나타낸다. 첫번째 2번째 인덱스는 좌표를 나타내고 마지막 인덱스는 벽을 몇개부순상태인지를 나타낸다.

BFS를 실시하는데 만약 crash변수값이 설정된 최대로 부술수 있는 벽의 개수보다 작은 경우와 최대로 부술수 있는 벽의 개수일때 2가지로 나눠서 생각한다. 나머지는 아래 소스코드를 보며 이해하길 바란다.

 

소스코드

import java.util.*;
import java.io.*;
class Node{
	int y;
	int x;
	int count;
	int crash;
	Node(int y,int x,int count,int crash)
	{
		this.x=x;
		this.y=y;
		this.count=count;
		this.crash=crash;
	}
}
	public class Main {

		public static int[][] map;
		public static boolean[][][] visited;
		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 N=Integer.parseInt(s[0]);
			int M=Integer.parseInt(s[1]);
			int K=Integer.parseInt(s[2]);
			map=new int[N][M];
			visited=new boolean[N][M][K+1];
			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]);
				}
			}//맵 입력
			Queue<Node> q=new LinkedList<Node>();//벽 부수기전의 큐
			q.add(new Node(0,0,1,0));//마지막이 부쉈는지 확인
			for(int i=0;i<=K;i++)
			{
				visited[0][0][i]=true;
			}
			int[] nx= {0,1,0,-1};
			int[] ny= {1,0,-1,0};
			int ans=Integer.MAX_VALUE;
			while(!q.isEmpty())
			{
				Node temp=q.poll();
				int temp_y=temp.y;//x좌표
				int temp_x=temp.x;//y좌표
				int temp_count=temp.count;
				int temp_crash=temp.crash;
				if(temp_x==M-1&&temp_y==N-1)
				{
					ans=temp.count;
					break;
				}//도착점 도착시 break
				for(int i=0;i<4;i++)
				{
					int y=temp_y+ny[i];
					int x=temp_x+nx[i];
					if(0<=y&&y<N&&0<=x&&x<M)//맵안에 있을경우
					{
						if(temp_crash<K)//벽을 부순횟수가 K보다 작다면
						{
							if(map[y][x]==1)//벽이 있다면
							{
								if(!visited[y][x][temp_crash+1])
								{
									visited[y][x][temp_crash+1]=true;
									q.add(new Node(y,x,temp_count+1,temp_crash+1));
								}
								
							}
							else//벽이 없다면
							{
								if(!visited[y][x][temp_crash])
								{
									visited[y][x][temp_crash]=true;
									q.add(new Node(y,x,temp_count+1,temp_crash));
								}
								
							}
						}
						else//벽을 최대로 부쉈다면
						{
							if(map[y][x]==0)
							{
								if(!visited[y][x][temp_crash])
								{
									visited[y][x][temp_crash]=true;
									q.add(new Node(y,x,temp_count+1,temp_crash));
								}
							}
						}
					}					
				}
			}//벽을 안부순 케이스 검사
			if(ans==Integer.MAX_VALUE)//도착점에 못도착함
			{
				System.out.println("-1");
			}
			else
			{
				System.out.println(ans);//정답 출력
			}	
		}
	}

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

 

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