3109 - Java

내 풀이

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

public class Main {
	
	static char[][] arr;
	static boolean[][] visited; //true면 방문했음 pass불가
	static int r,c;
	static int[] dx = {-1,0,1};
	static int[] dy = {1,1,1};
	static int ans=0;
	static boolean complete; //연결했는지
	
	public static void main(String[] args) throws Exception {
		StringTokenizer st;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		arr = new char[r][c];
		visited = new boolean[r][c];
		
		for(int i=0; i<r; i++) {
			String str = br.readLine();
			for(int j=0; j<c; j++) {
				arr[i][j] = str.charAt(j);
			}
		}
		
		for(int i=0; i<r; i++) {
			complete = false;
			dfs(i,0);
		}
		System.out.println(ans);
	}

	private static void dfs(int x, int y) {
		//파이프 연결완료
		if(y == c-1) {
			visited[x][y] = true;
			complete = true;
			//값 추가
			ans++;
			return;
		}
		//3가지 방향 탐색
		for(int d=0; d<3; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
//			완성안됐을때만
			if(!complete && isPass(nx,ny)) {
				//갈수 있으면 지금거 true로 바꾸고 가기
				visited[x][y] = true;
				dfs(nx,ny);
			}
		}
		//3가지 방향 모두 안되면 되돌아가야함
		//완성이 안됐는데 돌아가면 false로 바꾸고 돌아가기
		if(!complete) visited[x][y] = false;
		return;
	}

	private static boolean isPass(int x, int y) {
		//범위 안에 있고
		if(0<= x && x < r && y < c) {
			//건물 아니면서 visited=false여야함
			if(arr[x][y] == '.' && !visited[x][y]) {
				return true;
			}
		}
		return false;
	}

}

계속해서 시간초과가 나서 틀린 문제

이 부분이 필요없었다.

방문했다가 안돼서 돌아가야 하는 상황이면 false로 바꿀 필요가 없었다.
왜냐하면 현재 좌표에서 안돼서 돌아가야 하는 상황이면 다른 상황에서도 그좌표는 또 돌아가야하니까 false로 바꿀 필요가 없는 것이었다.

저 부분만 지우니 시간초과를 해결하고 통과하였다

이 문제의 핵심은 하나 더 있었는데 갈 수 있는 방향 3개에 대하여 그리디로 우선순위를 주는 것이었다.