☞ 이런 식으로 계층 별로 비용을 같게 하는 것은 어떻게 구현해야 할까? 하나의 계층에서 4방 탐색을 통해 큐에 넣은 값들의 갯수 만큼만 다음 Loop에서 방문하며 값을 처리해야 한다. 위의 예시에서는 정중앙에서 사방 탐색 후, 미 방문 행렬이 4개가 나왔음으로, 2 번째 Loop에서는 4번의 반복만 계산해야 한다.
이런 식으로 계층 별로 동일한 비용이 계산되도록 하면은 맨 끝 점인 [N-1] [M-1] 행렬을 조회하면, 최소 비용으로 끝 점까지 왔을 때의 비용이 나온다.
3. 코드 분석
import java.io.*;
import java.util.*;
publicclassMain {
staticint N,M;
staticint [][] miro;
staticint [] idx = newint[] {-1,0,1,0};
staticint [] idy = newint[] {0,1,0,-1};
publicstaticvoidmain(String[] args)throws IOException{
BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));
StringTokenizerst=newStringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
miro = newint [N][M];
for (inti=0; i < N; i++) {
Strings= br.readLine();
for (intj=0; j < M; j++) {
miro[i][j] = Character.getNumericValue(s.charAt(j));
}
}
bfs(0,0);
System.out.println(miro[N-1][M-1]);
}
publicstaticvoidbfs(int startX, int startY){
ArrayDeque<Coordinate> aq1 = newArrayDeque<>();
aq1.add(newCoordinate(startX, startY));
miro[startX][startY] = -1; // 방문 처리intcnt=1;
while (!aq1.isEmpty()){
cnt++;
intQsize= aq1.size();
for (intk=0; k < Qsize; k++) {
Coordinatenow= aq1.poll();
for (inti=0; i < 4; i++) {
intnx= now.x + idx[i];
intny= now.y + idy[i];
if(nx>=0 && ny>=0 && nx < N && ny < M){
if(miro[nx][ny] == 1){
miro[nx][ny] = cnt;
aq1.add(newCoordinate(nx,ny));
}
}
}
}
}
}
}
classCoordinate {
int x;
int y;
publicCoordinate(int x, int y){
this.x = x;
this.y = y;
}
}
4. 성장하기
내 풀이의 경우 cnt라는 변수를 만들어, 해당 변수에 하나의 계층이 끝날 때마다 ++ 해서 비용을 계산했다. DO IT 알고리즘 책을 보니, 현재 조회 중인 행렬값 + 1 로 비용을 계산해서, 번거로이 변수를 할당하고, 변수에 ++이 되는 시점을 고민할 필요가 없게 되었다.
import java.io.*;
import java.util.*;
publicclassMain {
staticint N,M;
staticint [][] miro;
staticint [] idx = newint[] {-1,0,1,0};
staticint [] idy = newint[] {0,1,0,-1};
publicstaticvoidmain(String[] args)throws IOException{
BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));
StringTokenizerst=newStringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
miro = newint [N][M];
for (inti=0; i < N; i++) {
Strings= br.readLine();
for (intj=0; j < M; j++) {
miro[i][j] = Character.getNumericValue(s.charAt(j));
}
}
bfs(0,0);
System.out.println(miro[N-1][M-1]);
}
publicstaticvoidbfs(int startX, int startY){
ArrayDeque<Coordinate> aq1 = newArrayDeque<>();
aq1.add(newCoordinate(startX, startY));
while (!aq1.isEmpty()){
intQsize= aq1.size();
for (intk=0; k < Qsize; k++) {
Coordinatenow= aq1.poll();
for (inti=0; i < 4; i++) {
intnx= now.x + idx[i];
intny= now.y + idy[i];
if(nx>=0 && ny>=0 && nx < N && ny < M){
if(miro[nx][ny] == 1){
// ----- 사방 탐색 당하는 값 + 1 로 계층 비용 계산 ------
miro[nx][ny] = miro[now.x][now.y]+1;
aq1.add(newCoordinate(nx,ny));
}
}
}
}
}
}
}
classCoordinate {
int x;
int y;
publicCoordinate(int x, int y){
this.x = x;
this.y = y;
}
}