미로만들기 [백준 2665][JAVA][골드 4][BFS][PriorityQueue]

 

[광고 누르면 오늘의 행운 상승!!]

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

2665번: 미로만들기

우선순위 큐를 이용한 bfs와 
그냥 bfs 두가지 방법으로 풀었다.

1. 우선순위 큐를 이용한 방법 
- 메모리 13000KB, 시간 88ms

- 우선순위 큐를 이용하여 가장 적은수의 색깔을 변경한 요소를 전진시킨다.

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


public class Main {
	
	static class Player implements Comparable<Player>{
		int row, col, cnt, color;
		public Player(int row, int col, int cnt, int color) {
			this.row = row;
			this.col = col;
			this.cnt = cnt;
			this.color = color;
		}
		@Override
		public int compareTo(Player o) {
			return Integer.compare(this.color, o.color);
		}
	}
	
	static int dx[] = {-1,0,1,0};
	static int dy[] = {0,1,0,-1};
	static int[][] map;
	static boolean[][] visit;
	static int N,ans = Integer.MAX_VALUE;
	static PriorityQueue<Player> q = new PriorityQueue<>();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		
		map = new int[N][N];
		visit = new boolean[N][N];
		
		for (int i = 0; i < N; i++) {
			char[] ch = br.readLine().toCharArray();
			for (int j = 0; j < N; j++) {
				map[i][j] = ch[j]-'0';
			}
		}
		
		q.add(new Player(0,0,0,0));
		bfs();
		
	}
	private static void bfs() {
		
		visit[0][0] = true;
		while(!q.isEmpty()) {
			Player player = q.poll();
			
			for (int i = 0; i < 4; i++) {
				int nx = player.row + dx[i];
				int ny = player.col + dy[i];
				
				if(nx< 0 || nx >= N || ny < 0 || ny >= N) continue;
				
				if(nx == N-1 && ny == N-1) {
					System.out.println(player.color);
					return;
				}
				
				//검은방일 때
				if(visit[nx][ny]) continue;
				
				if(map[nx][ny] == 0) {
					visit[nx][ny] = true;
					q.add(new Player(nx,ny,player.cnt+1,player.color+1));
				}
				//흰방일 때
				else if(map[nx][ny] == 1) {
					visit[nx][ny] = true;
					q.add(new Player(nx,ny,player.cnt+1,player.color));
				}
			}
		}
	}
}

 

2. 기본 BFS (더 느림)
메모리 19000KB 시간 112ms

- visit배열을 int로 생성하여 이동할 때 자신이 색깔을 변경한 횟수를 갱신시킨다.
- 횟수가 더 적다면 갱신시키고 횟수가 더 높다면 이동하지 않는다.

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


public class Main {
	
	static class Player{
		int row, col, cnt, color;
		public Player(int row, int col, int cnt, int color) {
			this.row = row;
			this.col = col;
			this.cnt = cnt;
			this.color = color;
		}
	}
	
	static int dx[] = {-1,0,1,0};
	static int dy[] = {0,1,0,-1};
	static int[][] map;
	static int[][] visit;
	static int N,ans = Integer.MAX_VALUE;
	static Queue<Player> q = new LinkedList<>();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		
		map = new int[N][N];
		visit = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			char[] ch = br.readLine().toCharArray();
			for (int j = 0; j < N; j++) {
				map[i][j] = ch[j]-'0';
				visit[i][j] = Integer.MAX_VALUE;
			}
		}
		
		q.add(new Player(0,0,0,0));
		
		bfs();
		System.out.println(visit[N-1][N-1]);
		
	}
	private static void bfs() {
		
		visit[0][0] = 0;
		while(!q.isEmpty()) {
			Player player = q.poll();
			
			for (int i = 0; i < 4; i++) {
				int nx = player.row + dx[i];
				int ny = player.col + dy[i];
				
				if(nx< 0 || nx >= N || ny < 0 || ny >= N) continue;
			
				//방문할 곳이 자기가 바꾼 횟수보다 작거나 같으면(불필요한 방문)
				if(visit[nx][ny] <= player.color) continue;
				//검은방일 때
				if(map[nx][ny] == 0) {
					visit[nx][ny] = player.color+1;
					q.add(new Player(nx,ny,player.cnt+1,player.color+1));
				}
				//흰방일 때
				else if(map[nx][ny] == 1) {
					visit[nx][ny] = player.color;
					q.add(new Player(nx,ny,player.cnt+1,player.color));
				}
			}
		}
	}
}