미로의 최단거리 통로
미로의 최단거리 통로
이전 문제와 동일
입력 설명
첫 번째 줄부터 7*7 격자의 정보가 주어집니다.
출력 설명
첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1를 출력한다.
입력
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 0
출력
12
틀린 구현 코드
final static int N = 7;
static int answer = Integer.MAX_VALUE;
static int[][] board = new int[N+1][N+1];
static int[] dir_x = {-1,0,1,0};
static int[] dir_y = {0,1,0,-1}; //6시 -> 3시 -> 12시 ->9시 방향
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
for(int i=1;i<N+1;i++){
for(int j=1;j<N+1;j++){
board[i][j] = in.nextInt();
}
}
board[1][1] = 1;
dfs(1,1,0);
System.out.println(answer);
}
static void dfs(int row,int col,int sum){
if(sum>8*8){
System.out.println("냥");
answer = -1;
return;
}
if(row==N && col ==N){
if(answer>=sum) {
answer = sum;
return;
}
}
else{
//방향보면서 뻗어나가야함
for(int i=0;i<4;i++){
int nx = row+dir_x[i];
int ny = col+dir_y[i];
if(nx>=1 && nx<=7 && ny>=1 && ny<=7 && board[nx][ny]==0){
//경계선 내부에 있고 갈수 있는 지점인지
board[nx][ny] = 1;
dfs(nx,ny,sum+1);
board[nx][ny] = 0;
}
}
}
}
길이 없어서 닶이 -1이 되는 경우를 어떻게 걸러주지 모르겠어서 처음 해본건 길이 없다면 이리저리 돌테니까 길의 가중치 총합이 8x8인 값을 넘겠지?라는 생각에 sum>88이라는 조건을 걸었음.
문제는 시작 지점에서 얼마 못가서 더이상 갈 길이 없을 수 있음. 따라서 sum>88은 터무니 없는 조건. bfs문제인데 dfs로 풀려해서 더 복잡해졌던 것 같음. 최소문제는 무조건 bfs임을...그리고 queue를 꼭...쓸 것...
모범답안 참고 후 구현 코드
final static int N = 7;
static int answer = -1;
static int[][] board = new int[N+1][N+1];
static int[] dir_x = {-1,0,1,0};
static int[] dir_y = {0,1,0,-1}; //6시 -> 3시 -> 12시 ->9시 방향
static Queue<Point> queue = new LinkedList<>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
for(int i=1;i<N+1;i++){
for(int j=1;j<N+1;j++){
board[i][j] = in.nextInt();
}
}
queue.offer(new Point(1,1));
bfs();
System.out.println(answer);
}
static void bfs(){
while(!queue.isEmpty()){
Point p = queue.poll();
for(int i=0;i<4;i++){
int nx = p.x +dir_x[i];
int ny = p.y +dir_y[i];
if(nx>=1 && nx<=7 && ny>=1 && ny<=7 && board[nx][ny]==0){
//경계선 내부에 있고 갈수 있는 지점인지
board[nx][ny] = board[p.x][p.y]+1;
queue.offer(new Point(nx,ny));
}
}
}
if(board[N][N] ==0) answer = -1;
else answer = board[N][N];
}
static class Point {
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
검사하는 조건은 같고 지금 좌표 = 이전 좌표 + 1; 해가면서 좌표값을 업데이트해주면 됨. bfs라서 queue가 empty가 될때까지 while문 돌면서 진행.
만약 최종 지점으로 갈 길이 없는 경우에는 최종좌표값이 0으로 남아있을 거니까 그런 경우에는 -1을 넣어줌.
Author And Source
이 문제에 관하여(미로의 최단거리 통로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yonii/미로의-최단거리-통로저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)