G3109. 빵집

문제

제출 코드

• 변경 전) 문제 접근 방식이 잘못되어서 처음에 복잡하게 코드를 짰다

  • 어느 열부터 파이프를 연결하냐에 따라 결과가 달라진다고 생각하여, 순열로 파이프 연결 시작할 행의 순서를 정한 뒤 백트래킹으로 연결되도록 했다
  • 백트래킹 과정에서 가봤던 길 표시하는 칸도 따로 만들어 둠

  • 1차 코드

    package gold;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class G3109_bakery {
    
    	static int R, C;
    	static int max;
    	static char[][] arr;
    	static boolean[][] isPipe;
    	static boolean[] selected;
    	static int[] list;
    	static int result = Integer.MIN_VALUE;
    
    	public static void main(String[] args) throws IOException {
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    		String[] line = br.readLine().split(" ");
    		R = Integer.parseInt(line[0]);
    		C = Integer.parseInt(line[1]);
    
    		arr = new char[R][C];
    		for(int i=0; i<R; i++) {
    			arr[i] = br.readLine().toCharArray();
    		}
    
    		max = 0;
    		isPipe = new boolean[R][C];
    		selected = new boolean[R];
    		list = new int[R];
    
    		perm(0);
    
    		System.out.println(result);
    	}
    
    	static void perm(int n) {
    		if(n==R) {
    			max = 0;
    			pipe(list[0], 0, 0);
    			result = Math.max(result, max);
    			return;
    		}
    
    		for(int i=0; i<R; i++) {
    			if(selected[i]) continue;
    			list[n] = i;
    			selected[i] = true;
    			perm(n+1);
    			selected[i] = false;
    
    		}
    	}
    
    	static void pipe(int r, int c, int idx) {	//list[i] = r값
    		if(r<0 || r>R-1 || arr[r][c] == 'x' || isPipe[r][c]) return;
    		else if(c>=C-1) {
    			max++;
    			if(++idx < R) pipe(list[idx], 0, idx);
    			return;
    		}
    
    		isPipe[r][c] = true;
    		pipe(r, c+1, idx);
    		pipe(r-1, c+1, idx);
    		pipe(r+1, c+1, idx);
    //		isPipe[r][c] = false;	//어차피 지금 안된 것들은 나중에 밟아도 안됨. 그러니 true놔둬서 다시 못밟게 하기
    								//그래서 이 문제는 사실 따로 배열 안만들고 원본배열 훼손해도 됨
    	}
    }
    

• 변경 후) 다른 문제를 풀고와서 보니 저번에 설명을 듣고 이해 안된 부분이 이해되었다

  • 다음 열로 나아가는 순서를 가장 위부터 탐색해서 최대한 파이프를 높게 연결하면, 행의 순서는 따로 고려하지 않고 가장 위의 행부터 파이프를 만들어주면 최대 값이 나온다
  • 이미 거쳐간 칸은 파이프가 연결되어 있거나, 더 나아가도 파이프를 연결할 수 없는 칸이기에, 파이프 탐색 과정에서 원본배열에 그냥 표시하면 됨. ⇒ 따로 배열을 만들 필요가 없었다

  • 2차 코드

    package gold;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    public class G3109_bakery {
    
    	static int R, C;
    	static int max = 0;
    	static boolean back;
    	static char[][] arr;
    
    	public static void main(String[] args) throws IOException {
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    		String[] line = br.readLine().split(" ");
    		R = Integer.parseInt(line[0]);
    		C = Integer.parseInt(line[1]);
    
    		arr = new char[R][C];
    		for(int i=0; i<R; i++) {
    			arr[i] = br.readLine().toCharArray();
    		}
    
    		for(int i=0; i<R; i++) {
    			back = false;
    			pipe(i, 0);
    		}
    		System.out.println(max);
    	}
    
    	/* 주어진 현재 위치에서 이어질 수 있는 위치로 파이프 연결
    	 * - r : 현재 열 번호
    	 * - c : 현재 행 번호
    	 */
    	static void pipe(int r, int c) {
    		if(back || r<0 || r>R-1 || arr[r][c] == 'x') return;
    		else if(c>=C-1) {
    			arr[r][c]='x';
    			max++;
    			back = true;
    			return;
    		}
    		pipe(r-1, c+1);
    		pipe(r, c+1);
    		pipe(r+1, c+1);
    
    		arr[r][c]='x';
    	}
    }