글 읽기 - 미로찾기 질문 있습니다!

cakimmy24 6년 전 0

최소길이를 출력하려면 저 length를 어디에 배치해야하나요?ㅠㅠ

아무리 머리를 굴려도 답이 안나오기에..

import java.util.LinkedList;
import java.util.Scanner;


public class Maze {

	public static void push(LinkedList<Integer> queue, int num){
		
		queue.offer(num);
		
	}
	
	public static int pop(LinkedList<Integer> queue){
		
		int tp = queue.poll();
		return tp;
		
	}
	
	public static int front(LinkedList<Integer> queue){
		
		return queue.getFirst();
		
	}
	
	public static int rear(LinkedList<Integer> queue){
		
		return queue.getLast();
		
	}
	
	public static boolean empty(LinkedList<Integer> queue){
		
		if(queue.isEmpty()) return true;
		else return false;
		
	}
	
	public static void BFS(char [][]maze, int [][]visit, int n, int m){
		
		LinkedList<Integer> queue = new LinkedList<Integer>();
		int direction[][] = {{1,0}, {0,-1}, {-1,0}, {0,1}};
		int length = 1;
		
		int curX, curY;
		
		push(queue, 1);
		push(queue, 1);
		visit[1][1] = 1;
		
		while(!empty(queue)){
			
			curX = pop(queue);
			curY = pop(queue);

			System.out.println("즁간길이점검: " + length);
			System.out.println("(" + curX + ", " + curY + ")");
			
			length ++; // 이 length요 ㅠㅠ
			
			for(int i = 0; i < 4; i ++){
				int tempX = curX + direction[i][0];
				int tempY = curY + direction[i][1];
				
				if(tempX == n && tempY == m){
					System.out.println("정답은: " + length);
					return ;
				}
				
				else if(tempX > 0 && tempX < n+1 && tempY > 0 && tempY < m+1 && maze[tempX][tempY] == '1' && visit[tempX][tempY] == 0){
					push(queue, tempX);
					push(queue, tempY);
					visit[tempX][tempY] = 1;
				}	
			}
			
		}
		
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		int m = in.nextInt();

		String temp[] = new String[n];
		char maze[][] = new char[n+2][m+2];
		int visit[][] = new int[n+2][m+2];
		
		for(int i = 0; i < n+2; i ++){
			for(int j = 0; j < m+2; j ++){
				if(i == 0 || i == n+1 || j == 0 || j == m+1){
					maze[i][j] = '0';
				}
			}
		}
		
		for(int i  = 0; i < n; i ++){
			temp[i] = in.next();
		}
		
		for(int i = 1; i < n+1; i ++){
			for(int j = 1; j < m+1; j ++){
				maze[i][j] = temp[i-1].charAt(j-1);
			}
		}
		
		for(int i = 0; i < n+2; i ++){
			for(int j = 0; j < m+2; j ++){
				if(i == 0 || i == n+1 || j == 0 || j == m+1){
					visit[i][j] = 1;
				}
				else visit[i][j] = 0;
			}
		}

		BFS(maze, visit, n, m);
				
	}

}

zlzmsrhak 6년 전 1

코드가 정확하지 않을 수 있으니 방향만 확인해보세요. (49, 73번째 줄)

import java.util.LinkedList;
import java.util.Scanner;
 
 
public class Maze {
 
    public static void push(LinkedList<Integer> queue, int num){
         
        queue.offer(num);
         
    }
     
    public static int pop(LinkedList<Integer> queue){
         
        int tp = queue.poll();
        return tp;
         
    }
     
    public static int front(LinkedList<Integer> queue){
         
        return queue.getFirst();
         
    }
     
    public static int rear(LinkedList<Integer> queue){
         
        return queue.getLast();
         
    }
     
    public static boolean empty(LinkedList<Integer> queue){
         
        if(queue.isEmpty()) return true;
        else return false;
         
    }
     
    public static void BFS(char [][]maze, int [][]visit, int n, int m){
         
        LinkedList<Integer> queue = new LinkedList<Integer>();
        int direction[][] = {{1,0}, {0,-1}, {-1,0}, {0,1}};
         
        int curX, curY;
         
        push(queue, 1);
        push(queue, 1);
        visit[1][1] = 1;
        int length[][] = new int[n+2][m+2];
         
        while(!empty(queue)){
             
            curX = pop(queue);
            curY = pop(queue);
 
//            System.out.println("즁간길이점검: " + length);
            System.out.println("즁간길이점검: " + length[curX][curY]);
            System.out.println("(" + curX + ", " + curY + ")");
             
            for(int i = 0; i < 4; i ++){
                int tempX = curX + direction[i][0];
                int tempY = curY + direction[i][1];
                 
                if(tempX == n && tempY == m){
                    System.out.println("정답은: " + length);
                    return ;
                }
                 
                else if(tempX > 0 && tempX < n+1 && tempY > 0 && tempY < m+1 && maze[tempX][tempY] == '1' && visit[tempX][tempY] == 0){
                    push(queue, tempX);
                    push(queue, tempY);
                    visit[tempX][tempY] = 1;
                    length[tempX][tempY] = length[curX][curY] + 1; // <- tempX, tempY 거리 갱신
                }   
            }
             
        }
         
    }
     
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        Scanner in = new Scanner(System.in);
         
        int n = in.nextInt();
        int m = in.nextInt();
 
        String temp[] = new String[n];
        char maze[][] = new char[n+2][m+2];
        int visit[][] = new int[n+2][m+2];
         
        for(int i = 0; i < n+2; i ++){
            for(int j = 0; j < m+2; j ++){
                if(i == 0 || i == n+1 || j == 0 || j == m+1){
                    maze[i][j] = '0';
                }
            }
        }
         
        for(int i  = 0; i < n; i ++){
            temp[i] = in.next();
        }
         
        for(int i = 1; i < n+1; i ++){
            for(int j = 1; j < m+1; j ++){
                maze[i][j] = temp[i-1].charAt(j-1);
            }
        }
         
        for(int i = 0; i < n+2; i ++){
            for(int j = 0; j < m+2; j ++){
                if(i == 0 || i == n+1 || j == 0 || j == m+1){
                    visit[i][j] = 1;
                }
                else visit[i][j] = 0;
            }
        }
 
        BFS(maze, visit, n, m);
                 
    }
 
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

미로찾기 질문 있습니다!

cakimmy24 6년 전 0

zlzmsrhak 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말