package algo.BFS;
import java.util.*;
import java.util.stream.IntStream;
public class BFS {
public static void main(String[] args) {
// [503], [503]
int board[][] = {
{1,1,1,0,1,0,0,0,0,0},
{1,0,0,0,1,0,0,0,0,0},
{1,1,1,0,1,0,0,0,0,0},
{1,1,0,0,1,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0}
}; //1파란칸, 0빨간칸
int vis[][] = new int[503][503]; //해당칸 방문
IntStream.range(0, 503)
.forEach(i -> {
Arrays.fill(vis[i], 0);
});
int n=7; int m=10; //n=행, m=열
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1}; //상하좌우
Queue<Pair> pQ = new LinkedList<Pair>();
vis[0][0] = 1;
pQ.add(new Pair(0, 0));
while(pQ.size() > 0){
Pair cur = pQ.peek(); pQ.remove();
System.out.println("("+cur.getX()+", "+cur.getY()+") -> ");
//방향 체크
for(int dir = 0; dir < 4; dir++){
int nx = cur.getX() + dx[dir];
int ny = cur.getY() + dy[dir];
if( nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(vis[nx][ny] == 1 || board[nx][ny] != 1) continue;
vis[nx][ny] = 1; //방문
pQ.add(new Pair(nx, ny));
}
}
}
}
class Pair implements Comparable<Pair>{
private int x;
private int y;
public Pair(int x, int y){
this.x = x;
this.y = y;
}
public int getX(){
return this.x;
}
public int getY(){
return this.y;
}
@Override
public int compareTo(final Pair o){
if(x == o.x) return Integer.compare(y, o.y);
return Integer.compare(x, o.x);
}
}
출처 : https://blog.encrypted.gg/941?category=773649