Inflearn Community Q&A
No author
This post's author information has been deleted.
BFS 코드 중에 이해가 안되는 부분이 있습니다.
Written on
·
213
0
import java.io.*;
import java.util.*;
class Solution {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
n = Integer.parseInt(br.readLine());
arr = new int[n][n];
check = new int[n][n];
check2 = new int[n][n];
Queue<Point> q = new LinkedList<>();
for(int i=0; i<n; i++){
String[] input = br.readLine().split(" ");
for(int j=0; j<n; j++){
arr[i][j] = Integer.parseInt(input[j]);
if(arr[i][j]==2) {
q.add(new Point(i, j, 0));
check2[i][j] = 1;
}
}
}
/**
* 3번 5번 케이스에서 하나씩 크게 결과가 나온다
*
* while (!q.isEmpty()){
* Point poll = q.poll();
*
* if(check[poll.x][poll.y] == 0){
* check[poll.x][poll.y] = 1;
* for(int j=0; j<4; j++){
* int nx = dx[j] + poll.x;
* int ny = dy[j] + poll.y;
* if(nx>=0 && ny>=0 && nx<n && ny<n && check[nx][ny] == 0 && arr[nx][ny] == 0){
* q.add(new Point(nx,ny, poll.cnt+1));
* res = Math.max(res, poll.cnt+1);
* }
* }
* }
* }
*/
while (!q.isEmpty()){
Point poll = q.poll();
for(int j=0; j<4; j++){
int nx = dx[j] + poll.x;
int ny = dy[j] + poll.y;
if(nx>=0 && ny>=0 && nx<n && ny<n && check2[nx][ny] == 0 && arr[nx][ny] == 0){
check2[nx][ny] = 1;
q.add(new Point(nx,ny, poll.cnt+1));
res = Math.max(res, poll.cnt+1);
}
}
}
System.out.println(res);
}
static int dx[]= {-1,1,0,0}, dy[]= {0,0,-1,1};
static int res = 0, n;
static int arr[][], check[][], check2[][];
static class Point{
int x, y, cnt;
Point(int a, int b, int c){
x=a; y=b; cnt=c;
}
}
}
주석 코드로 BFS를 돌리면 3번과 5번 케이스에서 실패합니다. 선생님의 코드를 참고해서 check 배열을 이용하는 검증부분만 순서를 바꿔서 해결했는데요.
결국 이해는 못해서 두가지 코드 모두 동일한 알고리즘으로 보입니다 ㅠㅠ 명쾌한 답변 가능할까요
Answer 1
0
안녕하세요, 인프런 AI 인턴입니다.
주석 처리된 코드와 주석을 해제한 코드 사이의 주된 차이점은 check 배열의 검증 시점에 있습니다. BFS를 사용할 때, 방문 처리를 언제 하는지는 중요한 요소 중 하나입니다.
주석 처리된 코드에서는 q.poll()을 호출한 후에 check 배열을 검사하고, 해당 위치를 방문하지 않았다면 (즉, check[poll.x][poll.y] == 0) 그 지점을 방문한 것으로 마킹합니다. 하지만 이 접근 방식은 큐에 동일한 위치가 여러 번 추가되는 것을 방지하지 않습니다. 왜냐하면, 한 위치가 큐에 추가되어도, 실제로 그 위치를 방문하고 (q.poll()을 통해) 검증하기 전까지는 다른 위치에서 그 지점을 다시 큐에 추가할 수 있기 때문입니다.
주석을 해제한 코드에서는 check2 배열을 이용하여 좀 더 조기에 방문 여부를 체크합니다. 즉, if 조건문 내에서 arr[nx][ny] == 0 && check2[nx][ny] == 0 검사를 통해 해당 위치가 아직 방문되지 않았고 갈 수 있는 곳임을 확인한 직후 바로 check2[nx][ny] = 1;로 방문 표시를 합니다. 이 방식은 해당 위치가 큐에 들어가기 전에 이미 방문된 것으로 마킹하기 때문에 같은 위치가 큐에 여러 번 추가되는 것을 효과적으로 방지합니다.
결론적으로, 두 코드의 차이는 방문 표시를 언제 하느냐에 있으며, 이는 BFS 알고리즘을 구현할 때 중복 방문을 방지하고 더 효율적으로 탐색을 수행하기 위한 중요한 요소입니다. 첫 번째 코드는 이 부분에서 비효율적이었으며, 두 번째 코드는 이 문제를 해결하여 모든 경우에 정상적으로 작동합니다.