0x09 - BFS
https://blog.encrypted.gg/941 + https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x09.md
의 문제들을 풀어봅니다.
* P1926 - 그림
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class P1926 {
public static int n; public static int m;
public static int[] dx = {1,-1,0,0};
public static int[] dy = {0,0,-1,1};
public static int[][] board;
public static int[][] visited;
public static Queue<Pair> q = new LinkedList<>();
public static int cnt =0;
public static int max = 0;
public static Pair cur;
public static void BFS() {
int b = 0;
q.offer(cur); // 0,0
while(!q.isEmpty()) {
cur = q.poll(); b++;
for(int dir=0;dir<4;dir++) {
int nx = cur.x+dx[dir];
int ny = cur.y+dy[dir];
if(nx<0 || nx>=n || ny<0 || ny>=m) {continue;}
if(board[nx][ny]==0 || visited[nx][ny]==1) {continue;}
visited[nx][ny]=1;
q.offer(new Pair(nx,ny));
}
}
if(b>max) {max=b;}
}
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());
board = new int[n][m];
visited = new int[n][m];
for(int i=0;i<n;i++) { //board 초기화
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<m;j++) {board[i][j] = Integer.parseInt(st.nextToken());}
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
cur = new Pair(i,j);
if(visited[i][j]==0 && board[i][j]==1) {
visited[i][j]=1;
BFS(); cnt++; }
}
}
System.out.println(cnt);
System.out.println(max);
}
static class Pair {
int x;
int y;
Pair(int x,int y) {
this.x = x; this.y=y;
}
}
}
- cnt : 그림의 개수를 세는 변수
- b : 현재 BFS를 그림의 너비를 저장하는 로컬변수
- max : 최대크기를 저장하는 변수
- board의 모든 점들에 BFS 수행 (아직 방문하지 않았고 && boar[i][j]==1인경우)
- 그림의 개수 = BFS()를 호출한 횟수
- 각 그림의 너비 : BFS()를 수행하면서 q.pop() 을 수행한 횟수
* P7576 - 토마토
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int[][] box; public static int[][] dist;
public static Queue<Pair> q = new LinkedList<>();
public static int[] dx = {1,-1,0,0};
public static int[] dy = {0,0,-1,1};
public static Pair cur;
public static int n; public static int m;
public static void BFS() {
while(!q.isEmpty()) {
cur = q.poll();
for(int dir=0;dir<4;dir++) {
int nx = cur.x+dx[dir];
int ny = cur.y+dy[dir];
if(nx<0 || nx>=n || ny<0 || ny>=m) {continue;} //범위밖
if(dist[nx][ny]!=-1 || box[nx][ny]==-1) {continue;} //이미방문했거나 토마토가 없으면
dist[nx][ny]= dist[cur.x][cur.y]+1;
q.offer(new Pair(nx,ny));
}
}
}
public static void main(String[] args) throws IOException {
int max=0;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
//box 초기화
m = Integer.parseInt(st.nextToken()); n = Integer.parseInt(st.nextToken());
box = new int[n][m]; dist = new int[n][m];
for(int i=0;i<n;i++) {
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<m;j++) {
int in = Integer.parseInt(st.nextToken());
box[i][j]=in; dist[i][j]=-1;
if(in==1) {q.offer(new Pair(i,j)); dist[i][j]=0;}
}
}
BFS();
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(box[i][j]==0 && dist[i][j]==-1) {max=-1; break;}
if(max!=-1) {max=Math.max(max,dist[i][j]);}
}
}
System.out.println(max);
}
public static class Pair {
int x; int y;
Pair(int x, int y) {this.x = x; this.y = y;}
}
}
- 여러 개의 시작점에서 + 거리를 구하는
- 큐에 시작점이 되는 위치를 넣어두고 → BFS를 돌리기- 큐의 성질 (BFS) : 들어온 순서대로 나오기 때문에, 큐에 처음에 들어있었던 위치(익은토마토)들로 부터 같은 거리에 있는 순서대로 큐에 담기게 된다 : 즉 큐에는 반드시 거리순으로 쌓이게 된다
0 1 2
1 2 / (0으로부터 거리가1)
2 / (0으로부터 거리가1) / (1로부터 거리가1)
(0으로부터 거리가1) / (1로부터 거리가1) / (2로부터 거리가1)
P1926번과 다른 점
- 여러 점에서 BFS를 수행한다는 점은 같지만
- 1926번은 이중for문으로 board를 순회하며 모든 점에서 BFS를 각각 수행
- 반면에 P7576번은 시작점을 큐에 넣어놓고 BFS를 한 번만 수행한다
→ 각 점들에서 부터의 최소거리를 구한다
- 거리 : dist[][] : 맨 처음에 전부 -1로 & 익은 토마토의 위치만 0으로 초기화
- 알게된 부분
- 처음엔 거리를 기록하려고 Pair에 변수를 추가하고.. 뭔 카운트를 올리고.. 별 걸 다해봤는데, 그냥 visited(방문여부기록) 배열에 거리를 표시하면서 & 방문여부도 기록하는게 제일 효율적이었고
- 루프마다 cnt++ 하는 방식은 "거리기록"이 아니라 순회를 할 때마다 값이 커져버리므로
dist[nx][ny]= dist[cur.x][cur.y]+1;지금 주변을 탐색하는 (cur) 좌표의 거리+1를 해주면 된다~
당연한 건데 돌아돌아 알게 됨 ^-^
* P4179 - 불!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int n; public static int m;
public static char[][] board; public static int[][] dist_f; public static int[][] dist_j;
public static Queue<Pair> q = new LinkedList<>();
public static int[] dx = {1,-1,0,0};
public static int[] dy = {0,0,-1,1};
public static Pair J;
public static void BFS_F() {
while(!q.isEmpty()) {
Pair cur=q.poll();
for(int dir=0;dir<4;dir++) {
int nx = cur.x + dx[dir];
int ny = cur.y+dy[dir];
if(nx<0 || nx>=n || ny<0 || ny>=m) {continue;}
if(board[nx][ny]=='#' || dist_f[nx][ny]!=-1) {continue;}//벽이거나 이미 옮긴경우
dist_f[nx][ny] = dist_f[cur.x][cur.y]+1;
q.offer(new Pair(nx,ny));
}
}
}
public static int BFS_J() {
while(!q.isEmpty()) {
Pair cur = q.poll();
for(int dir=0;dir<4;dir++) {
int nx = cur.x + dx[dir];
int ny = cur.y + dy[dir];
int distance = dist_j[cur.x][cur.y]+1;
//탈출성공
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
System.out.println(distance);
return 0;
}
//벽이거나 이미 불이 옮겼거나 이미 갔던곳인경우
if(board[nx][ny]=='#' || (dist_f[nx][ny]<=distance && dist_f[nx][ny]!=-1) || dist_j[nx][ny]!=-1) {continue;}
dist_j[nx][ny]=distance;
q.offer(new Pair(nx,ny));
}
}
System.out.println("IMPOSSIBLE");
return 0;
}
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());
board = new char[n][m]; dist_j = new int[n][m]; dist_f = new int[n][m];
for(int i=0;i<n;i++) {
String str = br.readLine();
for(int j=0;j<m;j++) {
board[i][j] = str.charAt(j);
dist_f[i][j]=-1; dist_j[i][j]=-1;
if (str.charAt(j)=='F') {
dist_f[i][j]=0; q.offer(new Pair(i,j));}
else if(str.charAt(j)=='J') {
J = new Pair(i,j);
dist_j[i][j]=0;
}
}
}
BFS_F();
q.offer(J);
BFS_J();
}
public static class Pair {
int x; int y;
public Pair(int x, int y) {this.x = x; this.y = y;}
}
}
- 불의 전파 + 지훈이의 이동 모두 BFS로 거리를 재야 함
- 다만, 불의전파 → 지훈이의이동 영향을 주므로
BFS_F → BFS_J 순서로 수행함- 탈춭조건 : 기존에는 범위를 벗어나는 것으로 간주해 continue 해버렸던 보드 밖으로 벗어나는 것 : nx < 0 || nx >= n
- 벽이거나 이미 불이 옮겼거나 이미 갔던곳인경우 : continue
- 중간에 탈출하지 못하고 q가 비게 되면 탈출불가
P4179 - 반례
4 4
###F
#J.#
#..#
#..#
와 같이 불이 지훈이보다 늦게 오는 곳 뿐만 아니라
불이 아예 옮겨붙지 않은 곳도 지나갈 수 있다
if(board[nx][ny]=='#' || dist_f[nx][ny]!=-1) {continue;}//벽이거나 이미 옮긴경우따라서 이렇게만 조건을 걸었을 때는 틀렸습니다를 봤다
*P1697 - 숨바꼭질
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class P1697 {
public static void main(String[] args) throws IOException {
int[] dist = new int[100005];
int[] dx = new int[3]; dx[0]=1; dx[1]=-1;
Queue<Integer> q = new LinkedList<>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken());
dist[n]=1; //시작점을 1로 두자
q.offer(n);
while(dist[m]==0) {
int cur = q.poll();
dx[2]=cur;
for(int dir=0;dir<3;dir++) {
int nx = cur+dx[dir];
if(nx>=100005 || nx<0) {continue;} //범위넘어감
if (dist[nx] != 0) {continue;} //이미 방문함
dist[nx] = dist[cur]+1;
q.offer(nx);
}
}
System.out.println(dist[m]-1);
}
}지금까지의 BFS는
상하좌우 - int[] dx = {1,-1,0,0}; int[] dy = {0,0,-1,1};
로의 전파였다면 이 문제는
+1, -1, *2로 전파하는 BFS라고도 볼 수 있다
- dx = {1, -1, cur} 로 둬서 +1, -1, *2로의 전파를 수행했다
P1697 - 반례
같은 곳에 있는 경우 : 0 0
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
boolean success = false;
int[] dist = new int[100005];
int[] dx = new int[3]; dx[0]=1; dx[1]=-1;
Queue<Integer> q = new LinkedList<>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken());
dist[n]=1; //초기화귀찮으니깐 시작점을 1로 두자
q.offer(n);
while(!success) {
int cur = q.poll();
dx[2]=cur;
for(int dir=0;dir<3;dir++) {
int nx = cur+dx[dir];
if(nx>=100000 || nx<0) {continue;} //범위넘어감
if(dist[nx]!=0) {continue;} //이미 방문함
if(nx==m) { //발견
System.out.println(dist[cur]);
success=true;
break;
}
dist[nx] = dist[cur]+1;
q.offer(nx);
}
}
}
}이렇게 하면 본인자리는 안 보고 +1, -1, *2만 보므로 발견하지 못한채 q가 비게 되므로 nullpointerException이 뜬다.
성공한 풀이를 보면 동생자리의 dist가 0이 아닌경우에만 반복하므로
동생과 같은 자리에 있다면 아예 반복문을 실행하지 않는다.
이래서 테스트케이스에만 묶여있는 조건을 걸지 않고 문제의 본질적인 종료조건을 생각해보는 것이 중요한 가보다
* P2583 - 영역 구하기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static Queue<Pair> q = new LinkedList<>();
public static int[][] board;
public static int[][] visited;
public static int[] dx = {1,-1,0,0};
public static int[] dy = {0,0,-1,1};
public static Pair cur;
public static int n; public static int m;
public static int cnt=0;
public static ArrayList<Integer> dists = new ArrayList();
public static void BFS() {
int dist=0;
while(!q.isEmpty()) {
cur = q.poll(); dist++;
for(int dir=0;dir<4;dir++) {
int nx = cur.x+dx[dir];
int ny = cur.y+dy[dir];
if(nx<0 || nx>=n || ny<0 || ny>=m) {continue;}
if(visited[nx][ny]==1 || board[nx][ny]==1) {continue;} //이미 방문햇거나 박스면
visited[nx][ny]= 1;
q.offer(new Pair(nx, ny));
}
}
dists.add(dist);
}
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
board = new int[n][m]; visited = new int[n][m];
for(int i=0;i<k;i++) {
int x1=0; int x2=0; int y1=0; int y2=0;
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<4;j++) { //board 초기화
if(j==0) {y1 = Integer.parseInt(st.nextToken());}
else if(j==1) {x1 = Integer.parseInt(st.nextToken());}
else if(j==2) {y2 = Integer.parseInt(st.nextToken())-1;}
else if(j==3) {x2 = Integer.parseInt(st.nextToken())-1;}
}
for(int j=x1;j<=x2;j++) {
for(int l=y1;l<=y2;l++) {
board[j][l]=1;
}
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(board[i][j]==0 && visited[i][j]==0) { //사각형이 아니고 && 방문하지 않은 곳
q.offer(new Pair(i,j)); visited[i][j]=1;
BFS();
cnt++;
}
}
}
sb.append(cnt).append('\n');
Collections.sort(dists);
ListIterator<Integer> iter = dists.listIterator();
while(iter.hasNext()) {sb.append(iter.next()).append(' ');}
System.out.println(sb);
}
public static class Pair {
int x; int y;
Pair(int x, int y) {
this.x = x; this.y = y;
}
}
}
- 문제에서 처리해야 할 부분들
- 입력받은 값들로 보드 구성하기
- 영역 개수 구하기 : BFS
- 영역 넓이 (거리가 아닌) 구하기 -> 오름차순으로 정렬 : BFS
-
입력 받은 값들로 보드 구성하기
- 입력받은 값을 차례로 y1, x1 / y2, x2로 저장
- x값은 열(2차원) / y값은 행임 (1차원)
- 입력 받는 값들은 점의 "좌표"이고 보드는 한 자리를 차지하는 배열이기 때문에 끝점은 -1을 더해 저장
- 왼쪽 아래가 원점이라 그냥 배열을 사용하면 모양은 예시와 다르게 뒤집어지지만, 크기와 개수를 구하는 데는 상관없으므로 그냥 사용
- 0 2 4 4 -> (2,0), (3,3)
- (x1, y1) ~ (x2, y2) 이중for문으로 1 채움
- 전체적으로 보면 삼중for문이라 괜히 생리적 불안감이 생기지만 어차피 각 수가 100 이하이므로 괜찮음
-
영역개수
이중for문으로 보드의 모든 지점 돌면서 BFS 수행
: 아직 방문하지 않고 && 1이 아닌(빈 곳) 지점을 queue에 넣고
bfs 수행할 때마다 영역개수++ -
영역 넓이
- 각 사각형에서 넓이 구하기
- queue에서 pop 할 때마다 dist++ : 넓이 증가
- 한 사각형 끝나고 나면 각 넓이들을 저장한 ArrayList에 add
- 가능한 모든 영역에 BFS를 끝낸 후에 넓이들이 저장된 ArrayList를 sort해서 오름차순으로 정렬
* P2667 - 단지번호붙이기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static Queue<Pair> q = new LinkedList<>();
public static int[][] board; public static int[][] visited;
public static int cnt=0;
public static ArrayList dists = new ArrayList();
public static int[] dx = {1,-1,0,0};
public static int[] dy = {0,0,-1,1};
public static int n;
public static void BFS() {
int dist = 0;
Pair cur;
while(!q.isEmpty()) {
cur = q.poll(); dist++;
for(int dir=0;dir<4;dir++) {
int nx = cur.x+dx[dir];
int ny = cur.y+dy[dir];
if(nx<0 || nx>=n || ny<0 || ny>=n) {continue;}
if(board[nx][ny]==0 || visited[nx][ny]==1) {continue;}
visited[nx][ny]=1;
q.offer(new Pair(nx,ny));
}
}
dists.add(dist);
}
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
board = new int[n][n]; visited = new int[n][n];
for(int i=0;i<n;i++) {
String str = br.readLine();
for(int j=0;j<n;j++) {
board[i][j] = str.charAt(j)-'0';
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(board[i][j]==1 && visited[i][j]==0) { //집이면서 && 방문하지 않은 곳
q.offer(new Pair(i, j)); visited[i][j]=1;
cnt++;
BFS();
}
}
}
Collections.sort(dists);
ListIterator iter = dists.listIterator();
sb.append(cnt).append('\n');
while(iter.hasNext()) {sb.append(iter.next()).append('\n');}
System.out.println(sb);
}
public static class Pair {
int x; int y;
Pair(int x, int y) {this.x = x; this.y = y;}
}
}2583과 너무너무 비슷한 문제
- 주어진 그대로 보드 초기화
- 1이고(집이고) && 아직방문하지 않았으면 BFS
- 각 거리들 ArrayList에 add 하고 마지막에 sort
* P5014 - 스타트링크
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
int cur; int next; int result=1;
StringBuilder sb = new StringBuilder();
Queue<Integer> q = new LinkedList<>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int f = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken()); //현재위치
int g = Integer.parseInt(st.nextToken()); //도착위치
int u = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int[] dir = {u, -d};
int[] building = new int[2*f+1];
building[s]=1;
q.offer(s);
while(!q.isEmpty() && building[g]==0) {
cur = q.poll();
for(int i=0;i<2;i++) {
next = cur+dir[i];
if(next<=0 || next>f) {continue;}
if(building[next]!=0) {continue;}
building[next]=building[cur]+1;
if(next==g) {result = building[next];}
q.offer(next);
}
}
if(building[g]!=0) {sb.append(result-1);}
else {sb.append("use the stairs");}
System.out.println(sb);
}
}P1697 - 숨바꼭질과 비슷한 문제다
그래서 틀린 것도 똑같은 부분에서 틀렸다ㅋㅋ
+u, -d를 탐색하는 BFS로 풀었다
P5014 반례 : 30프로에서 틀리는 경우
풀어놓고 보니 1697이랑 정말 똑같이 해서 틀렸다..
s==g인 경우가 반례였다
조건을 고치는게 애매해질 것 같아서 시작지점을 1로 하고 결과에서 -1을 해줬다.
* P2468 - 안전 영역
https://www.acmicpc.net/problem/2468
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class P2468 {
public static int n;
public static int cnt=0;
public static Queue<Pair> q = new LinkedList<>();
public static int[][] board; public static int[][] visited;
public static int maxH=0; public static int max=0;
public static int[] dx = {1,-1,0,0};
public static int[] dy = {0,0,-1,1};
public static Pair cur;
public static void BFS(int k) {
while(!q.isEmpty()) {
cur = q.poll();
for(int dir=0;dir<4;dir++) {
int nx = cur.x+dx[dir];
int ny = cur.y+dy[dir];
if(nx<0 || nx>=n || ny<0 || ny>=n) {continue;}
if(board[nx][ny]<=k || visited[nx][ny]!=0) {continue;}
visited[nx][ny]=1;
q.offer(new Pair(nx,ny));
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
board = new int[n][n]; visited = new int[n][n];
for(int i=0;i<n;i++) {
StringTokenizer st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<n;j++) {
board[i][j] = Integer.parseInt(st.nextToken());
maxH = Math.max(board[i][j],maxH);
}
}
for(int k=0;k<maxH;k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(board[i][j]>k && visited[i][j]==0) {
q.offer(new Pair(i,j));
BFS(k);
cnt++;
}
}
}
max = Math.max(cnt,max);
cnt=0;
for(int[] a : visited) {Arrays.fill(a,0);}
}
System.out.println(max);
}
public static class Pair {
int x; int y;
Pair(int x, int y) {this.x = x; this.y = y;}
}
}사실 처음엔 문제가 뭔지 정확히 이해를 못 했다
물 높이가 주어져야 영역을 구하는 게 아닌가? 라고 생각했었는데 그게 아니라 여러가지 물 높이가 주어졌을 때, 영역이 많아지는 최대영역을 구하는 것이다.
- 지형의 최대높이 이상의 강수는 어차피 의미가 없으므로, 지형 최대높이만큼 BFS를 돌려보고 지역개수가 최대가 되는 값을 구함
- 보드 초기화 하면서 지형의 최대높이 저장 : maxH
- 강수 높이 0 ~ maxH 까지 board에 대해 BFS 수행
- cnt : 해당 시행에서의 안전지역 개수
알게된 점
- Arrays.fill은 1차원 배열에만 가능하다
- 2차원 배열을 채우려면 위에처럼 1차원 단위로 채워줘야 함- BFS를 여러 번 수행해야 하는 경우 : 매 시행마다 cnt, visited 초기화 잊지말기
* P6593 - 상범빌딩
https://www.acmicpc.net/problem/6593
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int l, r, c;
public static int[][][] building; public static int[][][] visited;
public static Queue<Pair> q = new LinkedList<>();
public static int result=-1;
public static int[] dy = {1,-1,0,0,0,0};
public static int[] dz = {0,0,-1,1,0,0};
public static int[] dx = {0,0,0,0,1,-1};
public static Pair cur;
public static int BFS() {
while(!q.isEmpty()) {
cur = q.poll();
for(int dir=0;dir<6;dir++) {
int nx = cur.x + dx[dir];
int ny = cur.y + dy[dir];
int nz = cur.z + dz[dir];
if(nx<0 || nx>=l || ny<0 || ny>=r || nz<0 || nz>=c) {continue;}
if(visited[nx][ny][nz]!=0 || building[nx][ny][nz]=='#') {continue;}
visited[nx][ny][nz] = visited[cur.x][cur.y][cur.z]+1;
if(building[nx][ny][nz]=='E') {System.out.println("Escaped in "+(visited[nx][ny][nz]-1)+" minute(s)."); return -1;}
q.offer(new Pair(nx, ny, nz));
}
}
System.out.println("Trapped!");
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true) {
StringTokenizer st = new StringTokenizer(br.readLine()," ");
if(!st.hasMoreTokens()) { st = new StringTokenizer(br.readLine()); }
l = Integer.parseInt(st.nextToken());
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
if(l==0 && r==0 && c==0) {break;}
building = new int[l][r][c]; visited = new int[l][r][c];
for(int i=0;i<l;i++) {
for(int j=0;j<r;j++) {
String str = br.readLine();
if(str.equals("")) { str = br.readLine(); }
for(int k=0;k<c;k++) {
building[i][j][k] = str.charAt(k);
if(building[i][j][k]=='S') {q.offer(new Pair(i,j,k)); visited[i][j][k]=1;}
}
}
}
BFS();
q.clear();
}
}
static class Pair {
int x; int y; int z;
Pair(int x, int y, int z) {this.x = x; this.y = y; this.z = z;}
}
}
- x, y, z 3차원배열에 BFS를 적용하는 문제
- " 3차원 배열 + 각 점마다의 출발점에서의 거리 구하기 " 인 문제이다
16%에서 틀렸습니다
- 그냥 첫 번째 케이스부터 틀리는 것 같다
- 큐 초기화 안 함
- 입력 공백처리 오류
둘 중 하나일 것 같다
여긴 매 케이스마다 board,visited는 새로 할당되어 초기화 하지 않아도 된다고 안심했는데, 큐를 초기화 하는 것을 잊었다
!! BFS를 여러 번 수행하는 경우, 초기화를 절대 잊지 말자 !!
* P2206 - 벽 부수고 이동하기
https://www.acmicpc.net/problem/2206
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int[][] board; public static int[][][] dist;
public static Queue<Pair> q = new LinkedList<>();
public static Pair cur;
public static int[] dx = {1,-1,0,0};
public static int[] dy = {0,0,-1,1};
public static int n; public static int m;
public static int result;
public static void BFS() {
while(!q.isEmpty()) {
cur = q.poll();
for(int dir=0;dir<4;dir++) {
int nx = cur.x+dx[dir];
int ny = cur.y+dy[dir];
if(nx<0 || nx>=n || ny <0 || ny>=m) {continue;} //board 벗어나면
if(nx==(n-1) && ny==(m-1)) {result = Math.min(result,dist[cur.x][cur.y][cur.cnt]+1); break;} //목적지에 도착하면
if(dist[nx][ny][cur.cnt]!=0) {continue;} //이미 방문한 데면
//1이고 아직 안 부셨다면
if(board[nx][ny]==1 && cur.cnt==0) {
q.offer(new Pair(nx,ny,1));
dist[nx][ny][1] = dist[cur.x][cur.y][cur.cnt]+1;
continue;
}
if(board[nx][ny]==1 && cur.cnt!=0) {continue;}
dist[nx][ny][cur.cnt] = dist[cur.x][cur.y][cur.cnt]+1;
q.offer(new Pair(nx, ny,cur.cnt));
}
}
}
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());
result = n*m+1;
board = new int[n][m]; dist = new int[n][m][2];
for(int i=0;i<n;i++) {
String str = br.readLine();
for(int j=0;j<m;j++) {
board[i][j]=str.charAt(j)-'0';
}
}
if(n==1 && m==1) {result=1;} //출발지 = 도착지인 경우
else {
q.offer(new Pair(0, 0,0)); dist[0][0][0] = 1;
BFS();
}
if(result==(n*m+1)) {System.out.println("-1");}
else {System.out.println(result);}
}
public static class Pair {
int x; int y; int cnt;
public Pair(int x, int y, int cnt) {
this.x = x;
this.y = y;
this.cnt = cnt;
}
}
}
* P2573 - 빙산
https://www.acmicpc.net/problem/2573
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class P2573 {
public static int[][] board, visited, ex_board;
public static int n, m, nx, ny;
public static int result=0;
public static Queue<Pair> q = new LinkedList<>();
public static Queue<Pair> q_ice = new LinkedList<>();
public static int size; public static Pair cur;
public static int cnt=0;
public static int[] dx = {1,-1,0,0};
public static int[] dy = {0,0,-1,1};
public static void after() {
// 1. 1년후 상태 만들기
// 2. 덩어리 수 체크하기 : 개수만큼 cnt++
// 3. cnt>1이면 성공 / q_ice가 비면 불가능
// n, m < 300 : 배열크기 90000 / 빙하는 10000 이하 : 물이 80000 -> 빙하인 곳을 저장하자
// 1. 1년후 상태 만들기
//문제1. 같은 턴에 0이 돼버린 부분이 이웃한 빙산에 영향을 줌 : 1,1 -> 1,2
size=0;
while(size++<q_ice.size()) {
cur = q_ice.poll();
visited[cur.x][cur.y]=0;
for(int dir=0;dir<4;dir++) {
nx = cur.x+dx[dir];
ny = cur.y+dy[dir];
if(nx<0 || nx>=n || ny<0 || ny>=m) {continue;}
//바다 만난만큼 감소
if(ex_board[nx][ny]==0) {
if(board[cur.x][cur.y]>0) {board[cur.x][cur.y]-=1;}
}
}
q_ice.offer(cur);
}
//복사
for(int i=0;i< (size-1);i++) {
cur = q_ice.poll();
ex_board[cur.x][cur.y] = board[cur.x][cur.y];
if(board[cur.x][cur.y]!=0) { q_ice.offer(cur); }
}
}
// 2. 덩어리 수 체크하기
public static void BFS() {
cnt=0;
size = q_ice.size();
while(size-->0) {
int breadth=0;
cur = q_ice.poll();
q.offer(cur); q_ice.offer(cur);
while (true) {
cur = q.poll();
if(visited[cur.x][cur.y]!=1) {breadth++;}
for (int dir = 0; dir < 4; dir++) {
nx = cur.x + dx[dir];
ny = cur.y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {continue;}
if (visited[nx][ny] == 1 || board[nx][ny] == 0) {continue;}
visited[nx][ny]=1;
q.offer(new Pair(nx,ny));
}
//문제2. 끊어져서 q가 비었을때만 카운트 되는게 아니라 일단 q_ice의 모든 점을 조사하기 때문에 q_ice의 크기만큼 cnt++돼버림
if(q.isEmpty()) {
if(breadth!=0) {cnt++;}
break;
}
}
}
}
public static void main(String[] args) throws IOException {
int years=0;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken());
board = new int[n][m]; visited = new int[n][m]; ex_board = new int[n][m];
for(int i=0;i<n;i++) {
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<m;j++) {
board[i][j]=Integer.parseInt(st.nextToken());
ex_board[i][j] = board[i][j];
if(board[i][j]!=0) {q_ice.offer(new Pair(i,j));}
}
}
while(true) {
after(); years++;
BFS();
// 성공시
if(cnt>1) { System.out.println(years); break; }
// -> 전부 다 녹아버리면
if(q_ice.isEmpty()) { System.out.println(0); break; }
}
}
static class Pair {
int x; int y;
public Pair(int x, int y) {this.x = x;this.y = y;}
}
}
- board 상황대로 빙산 녹이기 (1년후 상황 만들기)
- 빙산 개수 세기 -> 전역변수 cnt 갱신
- cnt>1 : 성공 / q_ice.isEmpty : 빙산이 전부 녹으면 끝
- q_ice : 빙산이 있는 곳의 위치를 저장한 큐
- board : 빙산 상황 저장하느 보드
- ex_board : after()를 실행한 당시의 board를 기록
- visited : 빙산 개수세기에서 사용하는 방문여부를 기록하는 배열
- board 상황대로 빙산 녹이기 (1년후 상황 만들기)
- cur = q_ice.poll : 빙산위치에 대해서 전부 수행
1-1. 이 과정에서 q_ice의 요소를 전부 순회하므로, 다음에 빙산개수 판별에서 사용할 방문여부배열 visited를 0으로 초기화 함- ex_board 기준으로 주변에 사방에 있는 0개수 판별
- 실제 감소는 board에 수행
- 판별, 감소 끝냈으면 q_ice에 cur 다시 집어넣기
- board -> ex_board 복사
5-1. 이 과정에서 0이 돼버린 전 빙산의 위치는 q_ice에서 빼버림
- 빙산 개수 세기
- 끊어짐의 여부를 판단하는데 q.isEmpty를 활용하고 싶으므로
개수 탐색에 큐를 한 개 더 사용- 이번 탐색에 방문여부를 표시하는 visited, 바다여부를 판단해서 q에 넣음
- q가 비었고 && 너비가 있는(즉 이미 셌던 빙하가 아닌) 경우에 cnt++
- 녹이기 -> 개수세기 -> 결과판단
- cnt가 1이상이 되면 끊어졌다는 의미이
- 빙산이었던 자리가 다 녹아버리면 q_ice에서 빼버리므로 q_ice가 비면 전부 녹았다는 의미이므로 0 출력하고 끝
개수세기에서 보드 전체를 순회하고 싶지 않았고,
그래서 q_ice에 있는 요소들만 순회하고 싶어서 큐를 두 개 사용하다보니
이런 저런 오류가 생겨서 너비를 재는 변수도 쓰고 ex_board도 쓰고 ....
어찌저찌 풀긴 했는데 뭔가 굉장히 누덕누덕한 코드가 돼버렸다 ^-^..
- 반례
- 9 8
0 0 0 0 0 0 0 0
0 7 9 3 6 4 6 0
0 1 7 2 5 2 2 0
0 9 7 2 2 2 4 0
0 5 4 6 4 6 4 0
0 1 4 5 7 7 4 0
0 9 9 7 6 9 4 0
0 9 2 5 3 8 9 0
0 0 0 0 0 0 0 0
https://www.acmicpc.net/board/view/134531
- 시도마다 q_ice의 사이즈가 줄어서 ex_board를 갱신하는데 오류가 생겼음
- ex_board를 갱신할 때 q_ice.size()를 직접 쓰는게 아니라, size를 미리 저장한 변수를 사용해서 해결
- 5 5
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
- 50몇프로 언저리에서 NullPointerException이 발생했을 때 테스트 해봄
- 첫 시도에 전부 녹아서 q_ice가 비어버릴 때 오류가 발생했음
- 다시 생각해본 점
- 반복문으로 큐를 순회할때 q.size()를 변수로 쓰지말자
- 당연히 조건문에 따라 poll, offer를 하면 개수가 달라지므로 의도했던 것과 다른 작동이 일어날 수 있는데, 자꾸 간과하게 된다
* P2146 - 다리 만들기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class p2146 {
//1. map을 섬의 번호로 초기화한다
//2. 거리 재는 BFS 하다가 다른 섬으로 도착하면 기록 -> 최소값 갱신
static int n;
static int result;
static int[][] map, visited;
static Queue<Pair> q = new LinkedList<>();
static Pair cur;
static int[] dx = {1,-1,0,0};
static int[] dy = {0,0,-1,1};
static void BFS_cnt(int k) {
while(!q.isEmpty()) {
cur = q.poll();
for(int dir=0;dir<4;dir++) {
int nx = cur.x+dx[dir];
int ny = cur.y+dy[dir];
if(nx<0 || nx>=n || ny<0 || ny>=n) {continue;}
if(visited[nx][ny]==1 || map[nx][ny]==0) {continue;}
visited[nx][ny]=1; map[nx][ny]=k;
q.offer(new Pair(nx,ny));
}
}
}
static void BFS(int k) {
while(!q.isEmpty()) {
int cnt=0;
cur = q.poll();
//현재 최소거리보다 길어지면 어차피 탐색할 필요 X
if(cnt>visited[cur.x][cur.y]) {break;}
for(int dir=0;dir<4;dir++) {
int nx = cur.x+dx[dir];
int ny = cur.y+dy[dir];
if(nx<0 || nx>=n || ny<0 || ny>=n) {continue;}
if(visited[nx][ny]!=0 || map[nx][ny]==k) {continue;}
//다른 섬 만남
if(map[nx][ny]!=k && map[nx][ny]!=0) {result = Math.min(result,visited[cur.x][cur.y]);}
visited[nx][ny]=visited[cur.x][cur.y]+1;
q.offer(new Pair(nx,ny));
}
}
visited = new int[n][n];
}
static void clear() {
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
visited[i][j]=0;
}
}
}
public static void main(String[] args) throws IOException {
int k=1;
StringTokenizer st;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
map = new int[n][n]; visited = new int[n][n];
result=n*n;
for(int i=0;i<n;i++) {
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<n;j++) {
map[i][j]=Integer.parseInt(st.nextToken());
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(map[i][j]==1 && visited[i][j]==0) {
q.offer(new Pair(i,j));
visited[i][j]=1;
map[i][j]=k;
BFS_cnt(k);
k++;
}
}
}
clear();
//visited를 매 번 초기화해서 재사용?????
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(map[i][j]!=0 && visited[i][j]==0) {
q.offer(new Pair(i,j));
BFS(map[i][j]);
}
}
}
System.out.println(result);
}
static class Pair {
int x; int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}
- BFS로 섬마다 번호 붙이기 : BFS_cnt
- 각 점에서 BFS로 다른 섬까지의 최소거리 구하기
* P13549 - 숨바꼭질3
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int n, m, cur, next;
static int[] distance = new int[100001];
static Queue<Integer> q = new LinkedList<>();
static int[] dir = new int[3];
static boolean end = false;
static void BFS() {
while(!end) {
cur = q.poll();
if(cur==m) {
System.out.println(distance[cur]-1);
end = true;
break;}
dir[0] = cur;
for (int d = 0; d < 3; d++) {
next = cur + dir[d];
if(next>=100001 || next<0) {continue;}
if(distance[next]!=0) {continue;}
if(d!=0) {
q.offer(next);
distance[next] = distance[cur]+1;
}
else {
q.offer(next);
q.offer(cur);
distance[next] = distance[cur];
}
}
}
}
public static void main(String[] args) throws IOException {
dir[1]=-1; dir[2] = 1;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()," ");
n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken());
if(n==m) {
System.out.println(0);
} else {
q.offer(n); distance[n] = 1;
BFS();
}
}
}
- 탐색순서
: 비용이 없는 *2를 가장 먼저 탐색하고,
더 작아지는 선택지인 -1, 그 다음에 +1을 탐색한다
반례
- 44%
https://www.acmicpc.net/board/view/83938
0-1bfs
* P1600 - 말이 되고픈 원숭이
ㅜㅜ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class P1600 {
static int w, h, k, nx, ny;
static int[][] board; static int[][][] distance;
static Pair cur;
static int result;
static Queue<Pair> q = new LinkedList<>();
static int[] dx = {1,-1,0,0};
static int[] dy = {0,0,-1,1};
static int[] hx = {2,1,-2,-1,2,1,-2,-1};
static int[] hy = {1,2,1,2,-1,-2,-1,-2};
static int BFS() {
result = w*h;
if(w==1 && h==1) {
result=0;
return -1;
}
while(!q.isEmpty()) {
cur = q.poll();
if(cur.x==(h-1)&&cur.y==(w-1)) { result = distance[cur.x][cur.y][cur.cnt]; return -1; }
for(int dir=0;dir<4;dir++) {
nx = cur.x+dx[dir];
ny = cur.y+dy[dir];
if(nx<0 || nx>=h || ny<0 || ny>=w) {continue;}
if(board[nx][ny]==1) {continue;}
if(distance[nx][ny][cur.cnt]!=0) {continue;}
q.offer(new Pair(nx,ny, cur.cnt));
distance[nx][ny][cur.cnt] = distance[cur.x][cur.y][cur.cnt]+1;
}
if(cur.cnt<k) {
for (int dir = 0; dir < 8; dir++) {
nx = cur.x + hx[dir];
ny = cur.y+hy[dir];
if(nx<0 || nx>=h || ny<0 || ny>=w) {continue;}
if(board[nx][ny]==1) {continue;}
//메모리 초과 풀이
//if(distance[nx][ny][cur.cnt]!=0) {continue;}
if(distance[nx][ny][cur.cnt+1]!=0) {continue;}
q.offer(new Pair(nx,ny,cur.cnt+1));
distance[nx][ny][cur.cnt+1]=distance[cur.x][cur.y][cur.cnt]+1;
}
}
}
if(result==w*h) result=-1;
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
k = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine()," ");
w = Integer.parseInt(st.nextToken()); h = Integer.parseInt(st.nextToken());
board = new int[h][w]; distance = new int[h][w][k+1];
for (int i=0;i<h;i++) {
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<w;j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
q.offer(new Pair(0,0,0));
BFS();
System.out.println(result);
}
static class Pair {
int x, y, cnt;
public Pair(int x, int y, int cnt) { this.x = x; this.y = y; this.cnt = cnt; }
public Pair(int x, int y) { this.x = x; this.y = y; }
}
}나중에 BFS에 대한 모든걸 잊는다면 이걸 다시 풀어보면 될 것 같다
특정 조건에 따라 탐색하는 경로가 달라지는 조건이 걸린 문제다
( 정해진 횟수 만큼만 나이트 이동을 할 수 있음 )
따라서 x, y, 현재나이트이동횟수를 함께 기록하는 3차원 배열을 사용해야 한다
(무조건 visited 되었다고 방문할 수 없는 것이 아니라, 나이트이동횟수에 따라 경로가 달라지기 때문)
- 메모리초과
자꾸 메모리 초과가 떠서 3차원 배열이 문젠가..? 라는 허튼 의심을 했지만,
어딘가 잘못된 조건문을 써서 잘못된 탐색, 순회의 결과로 발생하는 것일 가능성이 높다....- 내가 틀렸던 부분
//메모리 초과 풀이 //if(distance[nx][ny][cur.cnt]!=0) {continue;} if(distance[nx][ny][cur.cnt+1]!=0) {continue;}
