[프로그래머스]경주로건설_Java

--문제--

https://programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

--문제 접근--

길 찾기 문제로서

처음 문제를 봤을 때 BFS로 풀면서 visit을 체크하면서 값이 작을 때 or 방문한 적이 없을 때만 que에 추가를 하면서 풀이를 진행하였습니다.

처음에 문제를 이해하기 위해 

위 사진의 경우 직선도로가 2개 코너가 4개라고 생각하였습니다.

그래서 맨 처음에는 실패하였고 코너에 직선도로가 무조건 포함된다고 생각하고 문제풀이를 진행하였습니다.

그리고 맨처음 시작할 때에 0,0에서 마지막점으로 이동하기 위해서는 오른쪽 혹은 아래로만 이동 가능하기 때문에 

Queue에 오른쪽과 아래로 이동이 가능하다면 Queue에 먼저 넣고 시작하였습니다,

그리하여 Queue를 돌때에 고려한 건 이미 간 적이 있는가 값이 더 작은 가를 고려하여 Queue를 체크하였습니다.

그리고 값을 체크할 때 낮은 값으로 최신화를 하기 위해 이동할 수 있는 곳들은 모두 값을 최대 값으로 설정해두고 시작하였습니다.

--코드--

package Level3;

import java.util.LinkedList;
import java.util.Queue;

public class 경주로건설 {
	static class node{
		int x,y,value,dir;
		public node(int x,int y,int value, int dir) {
			this.x=x;
			this.y=y;
			this.value=value;
			this.dir=dir;

		}
	}
	static int[] dr= {0,0,1,-1};
	static int[] dc= {1,-1,0,0};
	public static void main(String[] args) {
		int[][] temp= {{0, 0, 0, 0, 0, 0, 0, 0}, {1, 0, 1, 1, 1, 1, 1, 0},{1, 0, 0, 1, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 1, 1, 1}, {1, 1, 1, 1, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 1, 1, 0}, {1, 1, 1, 1, 1, 1, 1, 0}, {1, 1, 1, 1, 1, 1, 1, 0}};
		System.out.println(solution(temp));
	}
	//0은 오른쪽 1 왼쪽 2 아래 3 위쪽
	private static int solution(int[][] board) {
		int answer=Integer.MAX_VALUE;
		int[][] map=new int[board.length][board[0].length];
		Queue<node> que=new LinkedList<>();
		for(int i=0;i<board.length;i++) {
			for(int j=0;j<board[0].length;j++) {
				if(board[i][j]==0)map[i][j]=Integer.MAX_VALUE;				
			}
		}
		map[0][0]=0;
		if(board[0][1]==0) {
			que.add(new node(0,1,100,0));
			map[0][1]=100;
		}
		if(board[1][0]==0) {
			map[1][0]=100;
			que.add(new node(1,0,100,2));
		}
		boolean[][][] visit= new boolean[board.length][board[0].length][4];
		while(!que.isEmpty()) {
			node cur=que.poll();
			System.out.println(cur.x+" "+cur.y+" "+cur.value+" "+cur.dir);
			if(cur.x==board.length-1&&cur.y==board[0].length-1) {
				answer=Math.min(answer, cur.value);
			}
			for(int i=0;i<4;i++) {
				int dx=cur.x+dr[i];
				int dy=cur.y+dc[i];
				if(dx>=0&&dy>=0&&dx<board.length&&dy<board[0].length&&board[dx][dy]!=1) {
					if(cur.dir==i&&(cur.value+100<=map[dx][dy]||!visit[dx][dy][i])) {
						map[dx][dy]=cur.value+100;
						que.add(new node(dx,dy,cur.value+100,i));
						visit[dx][dy][i]=true;
					}
					else if(cur.dir!=i&&(cur.value+600<=map[dx][dy]||!visit[dx][dy][i])) {
							map[dx][dy]=cur.value+600;
							que.add(new node(dx,dy,cur.value+600,i));
							visit[dx][dy][i]=true;
					}
				}
			}
		}		
		return answer;
	}

}