[백준/3109][Java] 빵집

문제

https://www.acmicpc.net/problem/3109

3109번: 빵집

풀이

처음에는 BFS로 풀었는데 틀렸습니다.가 나왔다. 

구글링을 통해 왜 BFS가 아닌 DFS로 풀어야하는지에 대해 찾아보았다.

BFS를 사용하지 못하는 이유는 처음 지점부터 끝 지점까지 연결한 파이프는 한 줄이다.
따라서 오른쪽 위, 오른쪽, 오른쪽 아래 세 지점을 탐색해야하는데 만약 오른쪽 위 지점을 연결해서 쭉 이어가다 파이프 연결했으면 다시 돌아와서는 오른쪽과 오른쪽 아래 지점을 탐색할 수 없고 모든 파이프 지점에서 추가 탐색을 그만두게 해야한다.

그리고 최대 수를 찾는 것이 문제인데, 연결할 수 있는 가장 위로 붙여서 파이프를 설치한다면 아래에서 파이프를 연결할 수 있는 공간이 더 많이 생긴다. 따라서 맨 위부터 탐색하면 최대 개수를 구할 수 있다.

check 변수를 둬서 끝점까지 탐색을 완료하였을 때 현재 진행 중인 파이프의 재귀를 모두 다 종료를 해줘야한다. 
dfs를 새로 시작할 때마다 check변수를 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 {
	static char[][] board;
	static int n, m,cnt,check;
	static int[] dx = { -1, 0, 1 };
	//최대 수가 보장되는 이유: 연결할 수 있는 가장~ 위로 붙여서 파이프를 설치하다보면 
	//아래에서 파이프를 연결할 수 있는 공간이 더 많이 생기기 때문이다.
	//결국 이는 놓을 수 있는 파이프라인의 최대 개수가 된다.
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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];
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < m; j++) {
				board[i][j] = s.charAt(j);
			}
		}

		for(int i =0;i<n;i++) {
			check =0;// 한번 dfs 진행 후 초기화를 해줘야함
			dfs(i,0); //(0,0),(1,0), ... (n,0)에서 bfs 시작
		}
		System.out.println(cnt);
	}
	//BFS를 못사용 하는 이유는 처음 지점부터 끝 지점까지 연결한 파이프는 한 줄이다.
	//따라서 오위, 오, 오아 세 지점 탐색해야하는데 오른쪽 위 지점 연결해서 쭉 이어가다 파이프 연결했으면
	//오른쪽, 오른쪽 아래 지점을 탐색할 수 없으므로! 모든 파이프 지점에서 추가 탐색을 그만두게 해야한다.
	//https://maivve.tistory.com/240
    private static void dfs(int st, int e) {
        if(e==m-1) {
        	cnt++;
        	check=1;
        	return;
        }
        for (int i = 0; i < 3; i++) { //오른쪽위, 오른쪽, 오른쪽 아래 순서로 탐색
            int nx = st + dx[i];
            int ny = e + 1;
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(board[nx][ny]=='x') continue;
            board[nx][ny]='x';
            dfs(nx,ny);
            if(check==1) return;

        }

    }

}

 

틀린 코드

그리고.. 처음에 시도했던 BFS 방식. 예제는 맞으나 4%정도에서 틀렸습니다.가  뜬다.

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 char[][] board;
	static int[][] vis;
	static int n, m,cnt;
	static int[] dx = { -1, 0, 1 };
    static Queue<int[]> q = new LinkedList<>();

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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];
		vis = new int[n][m];
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < m; j++) {
				board[i][j] = s.charAt(j);
			}
		}

		for(int i =0;i<n;i++) {
			vis[i][0] = 1; //(i,0)은 방문 표시
			q.add(new int[] {i,0}); //큐에  (i,0) 삽입
			bfs(i,0); //(0,0),(1,0), ... (n,0)에서 bfs 시작
		}
		System.out.println(cnt);

	}
    private static void bfs(int st, int e) {
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0];
            int y = cur[1];
            for (int i = 0; i < 3; i++) { //오른쪽위, 오른쪽, 오른쪽 아래 순서로 탐색
                int nx = x + dx[i];
                int ny = y + 1;
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if(board[nx][ny]=='x') continue;
                if(ny==m-1) cnt++;
                board[nx][ny] = 'x';
                q.add(new int[]{nx, ny});
                break;
            }
        }
    }

}

솔직히 명확하게 이 코드가 어디서 문제가 생기는지는 모르겠어서 추후에 내용을 보충해보겠다.