이코테 - 미로탈출(BFS,DFS)

- 한 번에 갈 수 있는 최단거리를 구하는 게 목표이므로 BFS를 사용해서 문제를 풀었음

 

내가 짠 코드)

public class Test3 {
	
	// N,M (행,열) 
	static int n;
	static int m;
	// 미로 정보 ( 괴물칸 -> 0 , 괴물없는칸 -> 1) 
	static int[][] mazeInfo;
	// 방문여부 체크 (괴물이 없는 부분칸에서 방문했을경우 -> 1 , 방문안했을경우 -> 0) 
	static int[][] mazeCk;
	// 이동 가능한 방향 검사 순서 (우 -> 하 -> 좌 -> 상) 
	static int[] X = {0,1,0,-1};
	static int[] Y = {1,0,-1,0};
	// 최소 이동한 칸 개수 
	static int count = 0;
	
	// 최단거리로 미로 탈출하기 
	public static void bfs(int startX,int startY) {
		
		Queue<String> q = new LinkedList<>();
		q.offer(""+startX+startY); // 큐에 시작 좌표 넣기 
		
		int x=0,y=0; // 시작 좌표 
		while(!q.isEmpty()) {
			q.poll(); // 큐에서 데이터를 꺼냄
			// 해당 위치에서 최단거리로 가는 방향 검사 
			for(int i=0;i<4;i++) {
				int x1 = x + X[i];
				int y1 = y + Y[i];
				// 미로의 크기에서 벗어나는지 검사 
				if(x1 < 0 || x1 >= n || y1 < 0 || y1 >= m) continue;
				// 괴물칸이 아니고 방문여부가 없으면 캐릭터 이동시킨후 for문 탈출 
				if(mazeCk[x1][y1] == 0 && mazeInfo[x1][y1] == 1) {
					mazeCk[x1][y1] = 1; // 방문처리 
					x = x1;
					y = y1;
					q.offer(""+x+y); // 큐에 이동한 좌표 넣기 
					count++; // 칸이동 
					break;
				}
			}
			// 출구칸에 도착할 경우 
			if(x == n-1 && y == m-1){
				count++;
				break;
			}
		}
		
	}
	
	public static void main(String[] args){
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		try {
			// readLine()의 경우 Enter가 입력되기 전까지 문자열을 입력받음 
			String[] nums = br.readLine().split(" "); // 입력받은 문자들을 공백단위로 구분해서 문자열 배열에 넣어줌 
			n = Integer.parseInt(nums[0]);
	        m = Integer.parseInt(nums[1]);
			mazeInfo = new int[n][m];
			mazeCk = new int[n][m];
			
			// 미로 정보 입력 
			for(int i=0;i<n;i++) {
				String[] temp = br.readLine().split(""); // 공백없이 붙어서 입력함 
				for(int j=0;j<m;j++) {
					mazeInfo[i][j] = Integer.parseInt(temp[j]);
				}
			}

			// 최단거리로 미로탈출하는 메서드 호출
			bfs(0,0);
			
			System.out.println(count);
			
		} catch (IOException e) {
			e.printStackTrace();
		}
		
	}

}

 

다른 코드)

class Nodes{

    private int x;
    private int y;

    public Nodes(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return this.x;
    }
    
    public int getY() {
        return this.y;
    }
}
// 이코테 - 미로 탈출 
public class Main {
	
	// N,M (행,열) 
	static int n,m;
	// 미로 정보 ( 괴물칸 -> 0 , 괴물없는칸 -> 1) 
	static int[][] mazeInfo;
	// 이동 가능한 방향 검사 순서 (우 -> 하 -> 좌 -> 상) 
	static int[] X = {0,1,0,-1};
	static int[] Y = {1,0,-1,0};
	
	// 최단거리로 미로 탈출하기 
	public static int bfs(int startX,int startY) {
		
		Queue<Nodes> q = new LinkedList<>();
		q.offer(new Nodes(startX,startY)); // 큐에 시작 좌표 넣기 
		
		while(!q.isEmpty()) {
			Nodes node = q.poll(); // 큐에서 데이터를 꺼냄
			startX = node.getX();
			startY = node.getY();
			// 해당 위치에서 최단거리로 가는 방향 검사 (4가지 방향중 최단거리로 가는 방향)  
			for(int i=0;i<4;i++) {
				int x1 = startX + X[i];
				int y1 = startY + Y[i];
				// 미로의 크기에서 벗어나는지 검사 
				if(x1 < 0 || x1 >= n || y1 < 0 || y1 >= m) continue;
				// 괴물칸인 경우 
				if(mazeInfo[x1][y1] == 0) continue;
				// 처음 방문하는 칸일경우 최단 거리 기록하고 for문을 빠져나감
				if(mazeInfo[x1][y1] == 1) {
					mazeInfo[x1][y1] = mazeInfo[startX][startY] + 1;
					q.offer(new Nodes(x1,y1)); // 큐에 이동한 좌표 넣기  
					break; // 첫번째 시작위치가 다시 방문될 가능성이 있기때문에 break 구문으로 빠져나가줌
				}
			}
		}
		
		// 출구까지의 최단 거리 반환 
		return mazeInfo[n-1][m-1];
	}
	
	public static void main(String[] args){
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		try {
			// readLine()의 경우 Enter가 입력되기 전까지 문자열을 입력받음 
			String[] nums = br.readLine().split(" "); // 입력받은 문자들을 공백단위로 구분해서 문자열 배열에 넣어줌 
			n = Integer.parseInt(nums[0]);
	        m = Integer.parseInt(nums[1]);
			mazeInfo = new int[n][m];
			
			// 미로 정보 입력 
			for(int i=0;i<n;i++) {
				String[] temp = br.readLine().split(""); // 공백없이 붙어서 입력함 
				for(int j=0;j<m;j++) {
					mazeInfo[i][j] = Integer.parseInt(temp[j]);
				}
			}

			// 최단거리로 미로탈출하는 메서드 호출
			System.out.println(bfs(0,0));
			
		} catch (IOException e) {
			e.printStackTrace();
		}
		
	}

}

 

푸는 방법은 맞았지만 쓸데없는 여러 변수의 선언으로 메모리 공간을 낭비하고 있는 점에 대해서 주의하자

메모리 공간을 아끼기 위해서 최대한 변수를 적게 쓰는게 더 좋음 (***) 

 

클래스를 따로만들어서 사용하는 것으로 코드 상의 간결함? 줄 수 있는 거 같음 (*)

 

본격적으로 코드를 작성하기 전에 필요한 변수들을 먼저 선언해놓고 헷갈릴수 있으니 주석처리를 해놓는 습관을 가지자(**)