문제

BOJ 1189 컴백홈

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

훔훔...
오랜만에 수월하게 문제를 풀었다
사실 푼지는 좀 됐지만 안 올린 것을 발견하고 살짝 올려본다

알고리즘은 안풀릴 때는 증말 안풀리는데 가끔 이렇게 수월하게 풀리는 날에 느낄 수 있는 짜릿함 때문에 풀게 된다.

나는 짜릿한 감정을 매우 좋아한다.
왜냐? 나는 🎇🎉도파민 중독자🎊🧨니깐

하지만 빠르게 풀렸다고 코드가 좋은 것은 아니다 껄껄 당연하지
나는 깨끗하게 효율적이게 코드를 짤 줄 모르니깐

코드

package BOJ;

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

public class BOJ_1189_컴백홈 {
	
	static int R,C,K;
	static char [][]map;
	static int []dx= {0,1,-1,0};
	static int []dy= {1,0,0,-1};
	static boolean [][]visit;
	static int answer=0;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		R=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		K=Integer.parseInt(st.nextToken());
		
		map=new char[R][C];
		visit=new boolean[R][C];
		
		for(int i=0;i<R;i++) {
			map[i]=br.readLine().toCharArray();
			Arrays.fill(visit[i], false);
			
		}
		visit[R-1][0]=true;
		cal(R-1,0,1);
		
		System.out.println(answer);
	}
	
	static void cal(int y,int x,int cnt) {
		if(y==0&&x==C-1) {
			if(cnt==K)answer++;
			return ;
		}
		
		if(cnt>K)return ;
		
		for(int i=0;i<4;i++) {
			int ny=y+dy[i];
			int nx=x+dx[i];
			
			if(ny<0||nx<0||ny>=R||nx>=C||map[ny][nx]=='T'||visit[ny][nx]) {
				continue;
			}
			
			visit[ny][nx]=true;
			cal(ny,nx,cnt+1);
			visit[ny][nx]=false;
		}
	}
}

간략하게 설명하자면 나는 백트래킹을 사용해 문제를 풀었다.
나는 굉장히 일차원적인 사람이기에 백트래킹이나 완탐으로 문제를 많이 풀곤 한다.
나와 같은 경우 가지치기를 어떻게 하냐가 관건이다.

1.이동횟수가 이미 K를 넘겨버리면 바로 가차없이 짤

2.MAP을 넘거나 이미 들린 곳이라면 짤

암튼!
애니웨이!
끝~~