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개에 대하여 그리디로 우선순위를 주는 것이었다.
Author And Source
이 문제에 관하여(3109 - Java), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gothae/3109-Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)