🙋🏻♀️BFS 이용!
문제분석
N,M 최대가 100으로 매우 작기때문에 시간 제한은 별도로 생각안해도된다.
-> 따라서 DFS, BFS 둘 다 사용해도 됨
- 지나야 하는 칸 수의 최솟값 = 완전 탐색하며 몇 번째 깊이에서 원하는 값을 찾을 수 있는지 구하는것
-> 이 둘은 동일
이 문제는 BFS 이용해 최초로 도달했을 때 깊이 출력
BFS 적합 이유 = BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 다음 깊이로 넘어가기 때문
로직
2차원 배열에 데이터 저장
(0,0)에서 BFS 실행
상,하,좌,우 네 방향을 보며 인접한 칸을 본다 : 인접한 칸 숫자가 1이면서, 방문하지 않았으면 큐에 삽입
종료지점 (N-1, M-1)에서 BFS 종료하며 깊이 출력
Troubleshooting
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static char[][] A;
static Integer[][] depth;
static int[] dy = {1,0,-1,0};
static int[] dx = {0,1,0,-1};
static int count = 1;
static int N;
static int M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new char[N][M];
depth = new Integer[N][M];
//System.out.println("depth : " + depth[0][0]); // test
for(int i=0; i<N; i++) {
A[i] = br.readLine().toCharArray();
}
System.out.println(BFS(0,0));
}
public static int BFS(int y, int x) {
Queue<int[]> queue = new LinkedList<int[]>();
queue.add(new int[] {y,x});
depth[y][x] = count;
while(!queue.isEmpty()) {
int[] now = queue.poll();
count++;
for(int i=0; i<4; i++) {
int nextY = y + dy[i];
int nextX = x + dx[i];
if(0 <= nextX && 0 <= nextY && nextX < M && nextY < N ) {
if(depth[nextY][nextX] == 0) {
queue.add(new int[] {nextY, nextX});
depth[nextY][nextX] = count;
}
}
}
}
return depth[N-1][M-1];
}
}문제
원인
System.out.println("depth : " + depth[0][0]); 코드를 중간에 넣어서 확인해보니, null이 출력되는것을 확인할 수 있다!
int 배열인데, 초기에 0으로 초기화되는거아닌가..?
해결
Troubleshooting 2
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static char[][] A;
static Integer[][] depth;
static int[] dy = {1,0,-1,0};
static int[] dx = {0,1,0,-1};
static int count = 1;
static int N;
static int M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new char[N][M];
depth = new Integer[N][M];
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
depth[i][j] =0;
}
}
for(int i=0; i<N; i++) {
A[i] = br.readLine().toCharArray();
}
System.out.println(BFS(0,0));
}
public static int BFS(int y, int x) {
Queue<int[]> queue = new LinkedList<int[]>();
queue.add(new int[] {y,x});
depth[y][x] = count;
while(!queue.isEmpty()) {
int[] now = queue.poll();
count++;
for(int i=0; i<4; i++) {
int nextY = y + dy[i];
int nextX = x + dx[i];
if(0 <= nextX && 0 <= nextY && nextX < M && nextY < N ) {
if(depth[nextY][nextX] == 0) {
queue.add(new int[] {nextY, nextX});
depth[nextY][nextX] = count;
}
}
}
}
return depth[N-1][M-1];
}
}문제
결과가 다르게 출력된다.
원인
depth의 결과인데, BFS가 한번만 실행되고, 반복되지 않는것으로 보인다.
(0 = 방문하지않은 곳)
해결
-
A[y][x] == 1 일때만 방문할 수 있는데, 이 조건을 넣지않았다.
-> BFS - while - 이중 for문에서 두번째 for문에A[y][x] == 1이라고 추가했는데도 결과에 변화가 없었다..
-> A는 char형임에 주의했어야했다!!A[y][x] == 1->A[y][x] == '1'로 변경했다! -
또 반복문에서 변수사용에 오류가있었다. (이 실수를 계속한다..)
큐에서 poll하며 now에 저장했으니, 다음 y,x를 계산할 때 now를 사용해야한다!
int nextY = y + dy[i];
int nextX = x + dx[i];위에서 아래로 변경했다.
int nextY = now[0] + dy[i];
int nextX = now[1] + dx[i];Troubleshooting 3
문제
예제 1의 답은 15인데, 16으로 출력된다.
원인
depth를 살펴봤는데, 13 -> 15로 갑자기 건너뛴다..?!
count를 저기서 ++하면, 2개의 노드에 해당하는 인접노드를 한 번에 같이 체크해야할 때, 첫번째 나오는 노드의 인접노드와 두번째 나오는 노드의 인접노드의 count가 다르게 들어간다. (첫번째보다 두번째에 하나 더 크게 들어감)
해결
depth에 count를 넣는 코드 대신, poll하며 뺀 노드의 값에 +1 한 것을 넣는다. 즉, count 변수를 따로 만들어서 체크하는게아니라 배열에 있는 값을 이용한다.
depth[nextY][nextX] = count; -> depth[nextY][nextX] = depth[now[0]][now[1]] +1; 수정
제출코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static char[][] A;
static Integer[][] depth;
static int[] dy = {1,0,-1,0};
static int[] dx = {0,1,0,-1};
static int N;
static int M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new char[N][M];
depth = new Integer[N][M];
for(int i=0; i<N; i++) {
for(int j=0; j<M; j++) {
depth[i][j] =0;
}
}
for(int i=0; i<N; i++) {
A[i] = br.readLine().toCharArray();
}
System.out.println(BFS(0,0));
}
public static int BFS(int y, int x) {
Queue<int[]> queue = new LinkedList<int[]>();
queue.add(new int[] {y,x});
depth[y][x] = 1;
while(!queue.isEmpty()) {
int[] now = queue.poll();
for(int i=0; i<4; i++) {
int nextY = now[0] + dy[i];
int nextX = now[1] + dx[i];
if(0 <= nextX && 0 <= nextY && nextX < M && nextY < N ) {
if(depth[nextY][nextX] == 0 && A[nextY][nextX] == '1') {
queue.add(new int[] {nextY, nextX});
depth[nextY][nextX] = depth[now[0]][now[1]] +1;
}
}
}
}
return depth[N-1][M-1];
}
}주의할 점!
- 큐의 선언과 값 삽입 시 주의할 점
-
-> add를 이용해 배열을 넣기위해서는 Queue를 선언할 때 타입을 로 주는게아니라, <Integer[]>처럼 배열형식으로 넣어야한다!
-
에러 내용 :The method add(Integer[]) in the type Queue<Integer[]> is not applicable for the arguments (int[])-> queue에 int[] 형식으로 배열을 생성해서 삽입하니, 큐 선언시에도 <Integer[]>이 아닌, <int[]> 로 해야한다.
- depth를 계산하기위해, 입력받은 데이터 저장하는 A배열을 업데이트하는 방식을 사용한다. ( 따로 변수 사용x) : 한 번 queue.add 할때 동시에 들어가는 것들에 같은 depth 부여
숫자들이 붙어서 입력되면, 어떻게 처리해야할까?
내가 한 방법외에도 책에서 진행한 방법이 있어서 정리한다.
for(int i=0 ; i<N; i++){
st = new StringTokenizer(br.readLine());
String line = st.nextToken();
for(int j =0; j<M; j++){
A[i][j] = Integer.parseInt(line.substring(j, j+1));
}
}-> substring()이용해서 잘라준다.
