[BOJ]3109号:パン屋(Java)
質問する
3109号:パン屋
に答える
アルゴリズム:遡及、DFS
0行目では、任意の位置から出発することができるので、R長で回転し、深さ優先探索アルゴリズムを実行する.
ナビゲーションの基本条件は、現在のColumnが最後のColumnである場合です.
また,三方探索を行い,行く場所を特定した.
このとき、通ったところを「O」で表し、これ以上通ってはいけません.
パイプラインを作成する場合(基本的には)、Flagを使用してセル内での再ナビゲーションを防止します.(逆トレース)
実際、backtrackingの概念もよくわかりませんし、一般的な組み合わせアルゴリズムとDFSの違いも知りません.
歩く道が遠すぎる
コード#コード#
import java.io.*;
import java.util.*;
public class Main{
static int R, C, cnt;
static char[][] map; //맵 정보 저장
static int[] di = {-1,0,1}; //우상, 우, 우하
static int[] dj = {1,1,1};
static boolean flag = false; //백트래킹 flag
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char[R][C];
cnt = 0;
for(int i =0 ; i < R ; i++) {
String str = br.readLine();
for(int j =0 ; j < C ; j++) {
map[i][j] = str.charAt(j);
}
}
for(int i = 0 ; i< R ; i++) { //0행에서 R-1행까지 탐색
flag = false;
setPipe(i, 0); //깊이 우선 탐색
}
System.out.println(cnt);
}
private static void setPipe(int rowNo, int colNo) {
if(colNo == C-1) { //기저조건
map[rowNo][colNo] = 'O';
flag = true; //해당 경로에서의 경우의 수 탐색이 종료되었음을 알림
cnt++;
return;
}
for(int i =0 ; i < 3 ; i++) { //삼방탐색
int ni = rowNo + di[i];
int nj = colNo + dj[i];
if(0<=ni&&ni<R && 0<=nj&&nj<C && map[ni][nj] == '.') {
map[rowNo][colNo] = 'O';
setPipe(ni, nj); //깊이 우선 탐색
if(flag) return; //해당 경로에서 더이상 탐색하지 않도록
}
}
}
}
Reference
この問題について([BOJ]3109号:パン屋(Java)), 我々は、より多くの情報をここで見つけました https://velog.io/@dot2__/BOJ-3109번-빵집Javaテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol