[코딩테스트]BFS(미로찾기)

책 '이것이 취업을 위한 코딩 테스트다'를

기반으로 공부하였습니다.

https://github.com/ndb796/python-for-coding-test

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

 

1. 미로찾기 - 시작은 (1,1) 출구는 (n,m)

입력조건

- 첫재 줄에 두 정수 N, M(4<=N,M<=200)이 주어집니다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어집니다. 각각의 수들은 공백 없이 붙어서 입력으로 제시됩니다. 또한 시작 칸과 마지막 칸은 항상 1입니다.

출력조건

- 첫재 줄에 최소 이동 칸의 개수를 출력합니다.

 

작성코드(JAVA)

import java.util.*;

class Node_q {

    private int x;
    private int y;

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

    public int getX() {
        return this.x;
    }
    
    public int getY() {
        return this.y;
    }
}

public class test9_BFS {
	
	static int n,m;
	static int [][] data =new int[200][200];
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	
	
	public static int bfsq(int num, int num2) {
		Queue<Node_q> a = new LinkedList<Node_q>();
		a.offer(new Node_q(num,num2));
		while(!a.isEmpty()) {
			Node_q node = a.poll();
			int x = node.getX();
			int y = node.getY();
			for(int u=0;u<4;u++) {
				int nx = x+dx[u];
				int ny = y+dy[u];
				if((nx)>-1&&(nx)<n&&(ny)>-1&&(ny)<m) {
					if(data[nx][ny]==1) {
						data[nx][ny] = data[x][y]+1;
						a.offer(new Node_q(nx,ny));
					}
					if(!(data[nx][ny]==1)) {
						continue;
					}
				}
			}
		}
		return data[n-1][m-1];
	}
	
	public static void main(String[] args) {
		
		Scanner kb = new Scanner(System.in);
		n= kb.nextInt();
		m= kb.nextInt();
		kb.nextLine();
		for(int i=0;i<n;i++) {
			String a = kb.nextLine();
			for(int j=0;j<m;j++) {
				data[i][j]=a.charAt(j)-'0';
			}
		}
		System.out.println(bfsq(0,0));
	}

}

설명

- 해당 문제는 BFS로 접근하여 푸는 문제입니다. 시작점부터 한칸 이동할 때 마다 자신의 숫자를 다음 칸으로 넘겨 더해준다면 출구점까지 이동했을 때 해당 숫자를 반환하면 최소이동의 개수가 출력될 것입니다. 좌표를 표현해주기위한 객체 Node_q를 작성해주고 Queue를 이용하여 BFS탐색을 시작합니다.

 

 

( 이번 문제는 구현하는데 힘이 들어서 해설을 보며 코드를 작성했습니다. 처음에 변수를 어떤식으로 구성할지 막막했어서 구현하면서 계속 자료구조를 바꾸었던 것 같습니다. 처음 자료를 어떻게 구성할지 계획하는게 가장 중요한 포인트인것 같습니다. 이번에 부족한 점은 Queue를 어떻게 사용할 것인지, 값을 어떻게 더해갈 것인지 에서 생각이 짧았던것 같습니다. 이러한 문제점은 많은 문제들을 풀어가면서 해결할 수 있도록 노력하겠습니다! )