[백준 3109] 빵집- JAVA (solved.ac - 골드 2)

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

3109번: 빵집

풀이

문제를 보았을 때 알 수 있는 힌트

왼쪽에서 오른쪽으로 가는 선을 겹치지 않고 오른쪽 방향으로 위, 가운데 아래로 움직이며 끝까지 가게 하였을때 최대로 갈수있는 개수를 찾는 문제이다.

처음 봤을때 dfs로 풀면 되겠다. 끝까지 가는 것을 확인하고 백트래킹을 하면 되겠다 생각을 했다. 하지만 그렇게 구현을 하면 너무 많은 반복을 하게 된다. R이 10000이고 C는 500이나 되기에 무조건 시간 초과가 난다. 백트래킹으로는 절대 풀수 없는 문제였다.

좀더 문제를 읽고 생각을 해보면 간단한 문제였다. 먼저 위쪽, 가운데, 아래 방향으로 벽이거나 이미 지나간 곳이 아니라면 쭉 가게하고 끝까지 도착했다면 증가만 시키면 끝이 나는 문제였다.

왜냐하면 위쪽으로 파이프를 꽉꽉 채우면서 넣었기에 다시 백트래킹을 할 필요가 없다.

그래서 끝까지 도착한 값들만 증가 시키면 끝!이 난다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static int[] dx= {1,1,1};
	static int[] dy= {-1,0,1};
	static int r,c;
	static String[][] graph;
	static int[][] visited;
	static int result;
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] token = br.readLine().split(" ");
		r = Integer.parseInt(token[0]);
		c = Integer.parseInt(token[1]);
		graph = new String[r][c];
		visited = new int[r][c];
		for (int i = 0; i < r; i++) {
			token = br.readLine().split("");
			for (int j = 0; j < c; j++) {
				graph[i][j]=token[j];
			}
		}
		for (int i = 0; i < r; i++) {
				if(dfs(i,0)) {
					result++;
			}
			
		}
		System.out.println(result);
	}
	static boolean dfs(int y, int x) {
		
		for (int i = 0; i < 3; i++) {
			int vx = x+dx[i];
			int vy = y+dy[i];
			if(vx<c && -1<vx && vy<r && -1<vy) { 
				if(visited[vy][vx] == 0 && graph[vy][vx].equals(".")) {
					visited[vy][vx]=1;
					if(vx == c-1) return true;
					if(dfs(vy,vx)) return true;
				}
			}
		}	
		return false;
	}
}

이렇게 하면 문제는 통과가 되는데 1648ms가 나온다.

이를 해결하기 위해서 graph의 String을 char로 변경하고 visited를 graph로 합치는 작업을 진행하였다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static int[] dx= {1,1,1};
	static int[] dy= {-1,0,1};
	static int r,c;
	static char[][] graph;
	static int result;
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] token = br.readLine().split(" ");
		r = Integer.parseInt(token[0]);
		c = Integer.parseInt(token[1]);
		graph = new char[r][c];
		for (int i = 0; i < r; i++) {
			graph[i] = br.readLine().toCharArray();
		}
		for (int i = 0; i < r; i++) {
				if(dfs(i,0)) {
					result++;
			}
			
		}
		System.out.println(result);
	}
	static boolean dfs(int y, int x) {		
		for (int i = 0; i < 3; i++) {
			int vx = x+dx[i];
			int vy = y+dy[i];
			if(vx<c && -1<vx && vy<r && -1<vy) { // 그래프 안에 존재
				if(graph[vy][vx]=='.') {
					graph[vy][vx]='-';
					if(vx == c-1) {
						return true;
					}
					if(dfs(vy,vx)) {				
						return true;
					}
				}
			}
		}	
		return false;
	}
	
	static void printGraph() {
		for (char[] i : graph) {
			System.out.println(Arrays.toString(i));
		}
		System.out.println();
	}

}

이렇게 하니 결과적으로 296ms 까지 줄어들었다.

 

처음에 이해하는데 어려웠고 return시 boolean값으로 받으며 참인 경우 정답 값이 올라가게 해야하는 방식이라.. 다음에 이런 문제가 나오면 고민하여 풀어봐야할듯싶다.

비슷한 문제를 찾아서 풀어보는 것이 좋을 듯하다.

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/java/baekjoon3109/Main.java

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리