[백준] 14442 - 벽 부수고 이동하기 2(JAVA)

개츠비·2023년 3월 23일

목록 보기

41/84

소요시간 : 40분
문제 사이트 : 백준
문제 수준 : 골드 3
문제 유형 : 그래프 이론, 그래프 탐색, 너비 우선 탐색
다른 사람의 풀이를 참고 했는가 ? : X
한 번 풀었다가 다시 푸는 문제인가 ? : X
문제 링크 : https://www.acmicpc.net/problem/14442
푼 날짜 : 2023.03.23

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

BFS(너비 우선 탐색) 을 사용했다.

2. 사고과정

벽 부수고 이동하기 1을 먼저 풀고 왔기에 벽 부수고 이동하기 2도 BFS 문제라는 것은 확실하게 알고 있었다.
이 문제는 사실 이전 코드를 수정해서 전체적으로 다 푸는데에는 10분 - 15분 정도가 걸렸지만 TLE 가 나서 왜 날까 원인을 찾다가
그것을 잡는데만 25분을 썼다. 원인은 아주 간단하게
변수에다가 +1 을 실수로 안해줘서 중복탐색을 계속 해가지고 ... 였다

3. 풀이과정

만약 도착한 좌표가 벽이 아니라면 count를 1 증가시켜서 queue에 담기.
만약 도착한 좌표가 벽이라면, 벽을 1개 더 부술 수 있다면 벽을 부수고 count를 1 증가시켜서 queue에 담기.

4. 소스코드

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

class Node{
	int y;
	int x;
	int drill;
	int count;
	Node(int y,int x,int drill,int count){
		this.y=y;
		this.x=x;
		this.drill=drill;
		this.count=count;
	}
}
public class Main {
	static char map[][];
	static int xx[]= {-1,1,0,0};
	static int yy[]= {0,0,-1,1};
	static int cnt=-1;
	static int max=0;
	static StringBuilder sb=new StringBuilder();
	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());
		max=Integer.parseInt(st.nextToken());
		map=new char[n][m];

		for(int i=0;i<n;i++) {
			String line=br.readLine();
			for(int j=0;j<m;j++) {
				map[i][j]=line.charAt(j);
			}
		}

		bfs();

		System.out.println(cnt);

	}
	public static void bfs() {
		boolean visited[][][]=new boolean[map.length][map[0].length][max+1];
		for(int i=0;i<max;i++) {
			visited[0][0][i]=true;
		}
		Queue<Node> queue=new LinkedList<>();
		queue.add(new Node(0,0,0,1));
		while(!queue.isEmpty()) {
			Node temp=queue.poll();
			int prevY=temp.y;
			int prevX=temp.x;
			int drill=temp.drill;
			int count=temp.count;
			if(prevY==map.length-1&&prevX==map[0].length-1) {
				cnt=count;
				return;
			}
			for(int i=0;i<4;i++) {
				int nextY=prevY+yy[i];
				int nextX=prevX+xx[i];
				if(nextY<0||nextX<0||nextY>=map.length||nextX>=map[0].length) continue;

				if(map[nextY][nextX]=='0') { //빈칸이라면
					if(visited[nextY][nextX][drill]==false) { //방문한 적이 없다면
						queue.add(new Node(nextY,nextX,drill,count+1)); //count 를 1 증가시킴
						visited[nextY][nextX][drill]=true;  //방문처리
					}
				}
				else { //벽이라면
					if(drill+1<=max) {  //벽을 한 번 더 부술 수 있다면 drill을 1 증가시켜서 담음
						if(visited[nextY][nextX][drill+1]==false) {
							queue.add(new Node(nextY,nextX,drill+1,count+1));
							visited[nextY][nextX][drill+1]=true;
						}
					}
				}



			}
		}
	}
}