[이것이 코딩테스트다] 미로 탈출 - BFS 관련 문제

문제링크 : https://velog.io/@suzieep/Algorithm-%EC%9D%B4%EC%BD%94%ED%85%8C-%EB%AF%B8%EB%A1%9C-%ED%83%88%EC%B6%9C-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[Algorithm] (이코테) 미로 탈출 - 파이썬

 

 

5 6
101010
111111
000001
111111
111111

 

가로,세로(행과 열 {행거는 가로, 열쇠는 세로})로 기억합니다.

visited[][]를 사용하지 않고, graph 자체의 값에서 visited효과를 낼 수 있기에 그런방식으로 진행합니다.

 

class Node{
	private int x,y;
	public Node(int x, int y) {
		this.x=x;
		this.y=y;
	}
	public int getX() {
		return x;
	}

	public void setX(int x) {
		this.x = x;
	}

	public int getY() {
		return y;
	}

	public void setY(int y) {
		this.y = y;
	}
}

public class Main {

	public static int n,m;
	public static int[][] graph;
	
	public static int[] dy = {-1,1,0,0};
	public static int[] dx = {0,0,-1,1};
	
	public static void simulate() {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(0,0));
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			int x = node.getX();
			int y = node.getY();
			for(int dir=0;dir<4;dir++) {
				int nx = dx[dir] + x;
				int ny = dy[dir] + y;
				
				if(nx < 0 || nx >=n  || ny < 0 || ny >=m) continue;
				if(graph[nx][ny] == 0) continue;
				
				if(graph[nx][ny] == 1) {
					graph[nx][ny] = graph[x][y] + 1;
					q.offer(new Node(nx,ny));
				}
			}
		}
		System.out.println(graph[n-1][m-1]);
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n=sc.nextInt(); m=sc.nextInt();
		graph = new int[n+1][m+1];
		
		for(int i=0;i<n;i++) {
			String str = sc.next();
			for(int j=0;j<m;j++) {
				graph[i][j] = str.charAt(j)-'0';
			}
		}
		
		simulate();
		System.out.println(graph);
	}
}