[BJ] 21772 : 가희의 고구마 먹방

       문제 요약        

- 문제

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

21772번: 가희의 고구마 먹방

 

 

- 입출력

장애물 #

고구마 S

가희 G

 

         아이디어        

 

- 방문한 곳에 또 방문할 수 있다

- # 는 방문하지 못한다

 

T시간 만큼 움직였을 때, 먹을 수 있는 고구마의 최대 갯수를 구해야 한다

 

백트래킹에서 시간이 종료조건이 되고, 

상태가 변화는 작업은 고구마를 먹는 행위이다

 

따라서, (S -> . ) (. -> S) 작업을 잘 해줘야 한다

 

만약, 다음 위치에 고구마가 있다면

    고구마를 먹고 S => . 먹은 고구마 개수를 증가시킨 후 cnt+1 그곳으로 이동 (시간 증가, 함수 호출) 한다

고구마는 없지만 움직일 수있다면

   고구마 개수를 그대로 이동(시간증가, 함수 호출)한다

    

    

         소스코드        

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main {
	static int R,C,T;
	static char[][] box;
	static int curX, curY;
	static int[][] way = {{1,0}, {0,1}, {0,-1}, {-1,0}, {0,0}};
	static int maxSweetPotato = Integer.MIN_VALUE;
	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()); // 가로 크기
		T = Integer.parseInt(st.nextToken()); // 가희가 이동하는 시간
		
		box = new char[R][C];
		for(int r = 0; r < R; r++) {
			String str = br.readLine();
			for(int c = 0; c < C; c++) {
				box[r][c] = str.charAt(c);
				if(box[r][c] == 'G') { // 가희의 현재 위치 
					curX = r;
					curY = c;
				}
			}
		}

		// G : 가희의 현재 위치 
		back(0, curX, curY, 0);
		System.out.println(maxSweetPotato);
	}
	
	static void back(int time, int x, int y, int cnt) {
		if(time == T) {
			maxSweetPotato = Math.max(cnt, maxSweetPotato);
			return;
		}
		for(int w = 0; w < way.length; w++) {
			int nx = x + way[w][0];
			int ny = y + way[w][1];
			if(nx<0 || nx>= R || ny<0 || ny>= C) continue;
			if(box[nx][ny] == 'S') {
				box[nx][ny] = '.';
				back(time+1, nx, ny, cnt + 1);			
				box[nx][ny] = 'S';
			}else if(box[nx][ny]!='#'){
				back(time+1, nx, ny, cnt);
			}
		}
		
	}
	
}