[백준] 16993 벽 부수고 이동하기 3 - BFS + 방문처리 JAVA

passionfruit200 2023. 9. 11. 11:41

2023. 9. 11. 11:41

https://www.acmicpc.net/problem/16933

16933번: 벽 부수고 이동하기 3

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

www.acmicpc.net

코드설명

BFS 문제입니다.

이 문제에서 가장 유의해야할점들입니다.

시작점에서 현재 낮/밤인지 고려합니다.
1. 기준점에서 이동할 지점에서는 현재 낮/밤에서 반대로 밤/낮 으로 검사합니다.
만약 이동하지 못하는경우, 이동하지 않고 같은칸에 머물러있는것이 가능합니다.
1. 이때, 아무것도 안할경우의 처리하는것을 고려해야합니다. 처음에 저같은경우

아래의 반례를 이해한다면 풀 수 있습니다.

 3 3 3
011
111
110
 
정답:7
 
https://www.acmicpc.net/board/view/38832

처음에 틀렸던 코드의 주요로직을 살펴보겠습니다.

아래의 코드를 보면

map[nr][nc] == '0' (빈칸) 낮/밤 의 경우를 나누었습니다.

map[nr][nc] == '1' (벽) 낮/밤 의 경우를 나누었습니다.

여기서 발생하는 문제점은, 벽을 부순 이후에 본인의 위치에 계속 존재하려고할떄 발생합니다.

이유는, map[nr][nc] == '1'(벽)일떄 아침인경우는 다른 곳의 벽을 부술 수 있으니 이동한다고 가정합니다.

하지만, 저녁인경우 다른곳으로 이동이 불가능한데 이떄, 저는 dir = 0 ~ dir = 5 로 처리했으므로 모든 상하좌우현재위치 이렇게 5가지 방향을 모두 순회하므로 다른 방향으로도 벽을 부수지 않고 들어가기에 위의 제시한 예제의 답이 5로 나옵니다.

그렇기에 dir ==0 일떄, ( 현재 위치로 다시 움직일떄, 가만히 있을때 ) 벽의 위치에서 다시 존재할경우를 고려하면 됩니다.

조건문으로는 dir == 0 을 추가해주면됩니다.

 for(int dir=0;dir<5;dir++) {
    int nr = r + dx[dir];
    int nc = c + dy[dir];
    int nMorningZeroNightOne = morningZeroNightOne == 0 ? 1 : 0;
 
    if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
    if(map[nr][nc] == '0') { //벽이 아닐경우 그냥 이동합니다. 밤에도 이동가능합니다.
        if(morningZeroNightOne == 0) {
            if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount] == true) continue;
            visited[nr][nc][nMorningZeroNightOne][wallBreakCount] = true;
            q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount));	
        }
        else if(morningZeroNightOne == 1) {
            if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount] == true) continue;
            visited[nr][nc][nMorningZeroNightOne][wallBreakCount] = true;
            q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount));
        }
    }
 
    if(map[nr][nc] == '1') { //아침에만 부술 수 있습니다.
        if(morningZeroNightOne == 0) { //아침일경우 벽을 부술 수 있습니다.
            if(wallBreakCount >= K) continue; //이미 부술 수 있는 벽을 다 부쉈다면,
            if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount+1] == true) continue;
            visited[nr][nc][nMorningZeroNightOne][wallBreakCount + 1] = true;
            q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount + 1));	
        }
        else if(morningZeroNightOne == 1) { //저녁일경우 벽을 부수지 못하며, 다른곳으로 0 으로만 이동가능합니다.
            if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount] == true) continue;
            visited[nr][nc][nMorningZeroNightOne][wallBreakCount] = true;
            q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount));
        }
 
    }
 
}

dir==0을 개선한코드

 for(int dir=0;dir<5;dir++) {
    int nr = r + dx[dir];
    int nc = c + dy[dir];
    int nMorningZeroNightOne = morningZeroNightOne == 0 ? 1 : 0;
 
    if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
    if(map[nr][nc] == '0') { //벽이 아닐경우 그냥 이동합니다. 밤에도 이동가능합니다.
        if(morningZeroNightOne == 0) {
            if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount] == true) continue;
            visited[nr][nc][nMorningZeroNightOne][wallBreakCount] = true;
            q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount));	
        }
        else if(morningZeroNightOne == 1) {
            if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount] == true) continue;
            visited[nr][nc][nMorningZeroNightOne][wallBreakCount] = true;
            q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount));
        }
    }
 
    if(map[nr][nc] == '1') { //아침에만 부술 수 있습니다.
        if(morningZeroNightOne == 0) { //아침일경우 벽을 부술 수 있습니다.
            if(wallBreakCount >= K) continue; //이미 부술 수 있는 벽을 다 부쉈다면,
            if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount+1] == true) continue;
            visited[nr][nc][nMorningZeroNightOne][wallBreakCount + 1] = true;
            q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount + 1));	
        }
 
        if( dir == 0) {
            if(morningZeroNightOne == 1 ) { //저녁일경우 벽을 부수지 못하며, 다른곳으로 0 으로만 이동가능합니다.
                if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount] == true) continue;
                visited[nr][nc][nMorningZeroNightOne][wallBreakCount] = true;
                q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount));
            }    					
        }
 
 
    }
 
}

위와 같이 특정한 곳을 모두 고려하여 진행할 수도 있지만, 단순히 만약 dir == 0 이라면 벽이 존재하든 아니든 전혀 중요하지 않습니다. 그저 해당 위치에 존재하기만 하면 되니 아래와 같이 수정한다면 훨씬 깔끔한 코드가 탄생합니다.

좀 아쉬운점은 애초에 dir 상하좌우로 여전히 냅두고, 아예 바깥에다가 현재 위치를 삽입하는 방안으로 짯으면 헷갈리지 않았을 것 같습니다.

 for(int dir=0;dir<5;dir++) {
    int nr = r + dx[dir];
    int nc = c + dy[dir];
    int nMorningZeroNightOne = morningZeroNightOne == 0 ? 1 : 0;
 
    if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
    if(map[nr][nc] == '0') { //벽이 아닐경우 그냥 이동합니다. 밤에도 이동가능합니다.
        if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount] == true) continue;
        visited[nr][nc][nMorningZeroNightOne][wallBreakCount] = true;
        q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount));
    }
 
    if(map[nr][nc] == '1' && morningZeroNightOne == 0) { //아침에만 부술 수 있습니다.
        if(wallBreakCount >= K) continue; //이미 부술 수 있는 벽을 다 부쉈다면,
        if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount+1] == true) continue;
        visited[nr][nc][nMorningZeroNightOne][wallBreakCount + 1] = true;
        q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount + 1));
    }
 
    if(dir == 0) { //만약 아무것도 안움직일경우
        if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount] == true) continue;
        visited[nr][nc][nMorningZeroNightOne][wallBreakCount] = true;
        q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount));
    }
 
}

코드

정답코드

 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 Main {
	
	public static int N, M, K;
	public static char[][] map;
	public static boolean[][][][] visited;
	public static int[] dx= {0, -1,1,0,0};
	public static int[] dy = {0, 0,0,-1,1};
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	
    	visited = new boolean[N][M][2][K+1];
    	map = new char[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		map[i] = st.nextToken().toCharArray();
    	}
    	simulate();
    	if(answer == 0) {
    		System.out.println("-1");
    	}else {
    		System.out.println(answer);	
    	}
    	
    }
    
    public static void simulate() {
    	Queue<Node> q = new LinkedList<>();
    	q.offer(new Node(0, 0, 1, 0, 0));
    	visited[0][0][0][0] = true;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int r = temp.r;
    		int c = temp.c;
    		int moveCnt = temp.moveCnt;
    		int morningZeroNightOne = temp.morningZeroNightOne;
    		int wallBreakCount = temp.wallBreakCount;
			if(r == N-1 && c == M-1) {
				answer = moveCnt; 
				return ;
			}    		
    		for(int dir=0;dir<5;dir++) {
    			int nr = r + dx[dir];
    			int nc = c + dy[dir];
    			int nMorningZeroNightOne = morningZeroNightOne == 0 ? 1 : 0;
    			
    			if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
    			if(map[nr][nc] == '0') { //벽이 아닐경우 그냥 이동합니다. 밤에도 이동가능합니다.
    				if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount] == true) continue;
    				visited[nr][nc][nMorningZeroNightOne][wallBreakCount] = true;
    				q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount));
    			}
    			
    			if(map[nr][nc] == '1' && morningZeroNightOne == 0) { //아침에만 부술 수 있습니다.
    				if(wallBreakCount >= K) continue; //이미 부술 수 있는 벽을 다 부쉈다면,
    				if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount+1] == true) continue;
    				visited[nr][nc][nMorningZeroNightOne][wallBreakCount + 1] = true;
    				q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount + 1));
    			}
    			
    			if(dir == 0) { //만약 아무것도 안움직일경우
    				if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount] == true) continue;
    				visited[nr][nc][nMorningZeroNightOne][wallBreakCount] = true;
    				q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount));
    			}
    			
    		}
    		
    		
    	}
    	
    }
    
}
 
class Node{
	int r;
	int c;
	int moveCnt;
	int morningZeroNightOne = 0;
	int wallBreakCount = 0;
	public Node(int r, int c, int moveCnt, int morningZeroNightOne, int wallBreakCount) {
		this.r=r;
		this.c=c;
		this.moveCnt = moveCnt;
		this.morningZeroNightOne = morningZeroNightOne;
		this.wallBreakCount = wallBreakCount;
		
	}
}

틀린코드

 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 Main {
	
	public static int N, M, K;
	public static char[][] map;
	public static boolean[][][][] visited;
	public static int[] dx= {0, -1,1,0,0};
	public static int[] dy = {0, 0,0,-1,1};
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());
    	
    	visited = new boolean[N][M][2][K+1];
    	map = new char[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		map[i] = st.nextToken().toCharArray();
    	}
    	simulate();
    	if(answer == 0) {
    		System.out.println("-1");
    	}else {
    		System.out.println(answer);	
    	}
    	
    }
    
    public static void simulate() {
    	Queue<Node> q = new LinkedList<>();
    	q.offer(new Node(0, 0, 1, 0, 0));
    	visited[0][0][0][0] = true;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int r = temp.r;
    		int c = temp.c;
    		int moveCnt = temp.moveCnt;
    		int morningZeroNightOne = temp.morningZeroNightOne;
    		int wallBreakCount = temp.wallBreakCount;
			if(r == N-1 && c == M-1) {
				answer = moveCnt; 
				return ;
			}    		
    		for(int dir=0;dir<5;dir++) {
    			int nr = r + dx[dir];
    			int nc = c + dy[dir];
    			int nMorningZeroNightOne = morningZeroNightOne == 0 ? 1 : 0;
    			
    			if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
    			if(map[nr][nc] == '0') { //벽이 아닐경우 그냥 이동합니다. 밤에도 이동가능합니다.
    				if(morningZeroNightOne == 0) {
        				if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount] == true) continue;
        				visited[nr][nc][nMorningZeroNightOne][wallBreakCount] = true;
        				q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount));	
    				}
    				else if(morningZeroNightOne == 1) {
        				if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount] == true) continue;
        				visited[nr][nc][nMorningZeroNightOne][wallBreakCount] = true;
        				q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount));
    				}
    			}
    			
    			if(map[nr][nc] == '1') { //아침에만 부술 수 있습니다.
    				if(morningZeroNightOne == 0) { //아침일경우 벽을 부술 수 있습니다.
        				if(wallBreakCount >= K) continue; //이미 부술 수 있는 벽을 다 부쉈다면,
        				if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount+1] == true) continue;
        				visited[nr][nc][nMorningZeroNightOne][wallBreakCount + 1] = true;
        				q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount + 1));	
    				}
    				else if(morningZeroNightOne == 1) { //저녁일경우 벽을 부수지 못하며, 다른곳으로 0 으로만 이동가능합니다.
        				if(visited[nr][nc][nMorningZeroNightOne][wallBreakCount] == true) continue;
        				visited[nr][nc][nMorningZeroNightOne][wallBreakCount] = true;
        				q.offer(new Node(nr, nc, moveCnt + 1, nMorningZeroNightOne, wallBreakCount));
    				}
    				
    			}
    			
    			
    		}
    		
    		
    	}
    	
    }
    
}
 
class Node{
	int r;
	int c;
	int moveCnt;
	int morningZeroNightOne = 0;
	int wallBreakCount = 0;
	public Node(int r, int c, int moveCnt, int morningZeroNightOne, int wallBreakCount) {
		this.r=r;
		this.c=c;
		this.moveCnt = moveCnt;
		this.morningZeroNightOne = morningZeroNightOne;
		this.wallBreakCount = wallBreakCount;
		
	}
}

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 3055 탈출 - BFS JAVA (0)	2023.09.12
[백준] 16946 벽 부수고 이동하기 4 - BFS + 방문처리 + 시간초과 JAVA (0)	2023.09.11
[백준] 14442 벽 부수고 이동하기 2 - BFS + 방문처리 JAVA (0)	2023.09.11
[백준] 12886 돌 그룹 - BFS JAVA (0)	2023.09.10
[백준] 9019 DSLR - BFS JAVA (0)	2023.09.09

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

passionfruit200