[코드트리 챌린지] 3주차 ㅜㅜ

ㅜㅜ 퇴보했다 퇴보했다기보단 공부안한 백트래킹이 나와서 못풀었다 ..

저도 알아요 백트래킹 못하는거 ㅜㅜ.......
아 근데 지난주 bfs도 다 못풀었다고요 ,,,
왜그러냐면 ..

https://www.codetree.ai/missions/2/problems/clear-stones-well?&utm_source=clipboard&utm_medium=text

돌 잘치우기 너 ,,, 백트래킹 묻어있구나
그래서 사실 2주차에 이 문제를 맞닥뜨리고나서 풀기싫어서 안풀고 있었다..
왜냐면 풀줄 몰라서요 .. 이거 어떻게 하는건데

진짜 몰라서 처음에는 돌을 부실 수 있는 수만큼의 파워를 들고 bfs를 시작해서
돌을 만날때마다 파워만큼 치우고 visited 처리 시키기? 정도로 생각하고 풀었다. 그랬더니 bfs를 돌릴때마다 같은 돌만 부시게 된다는 사실을 뒤늦게 알았다.
ㅋㅋ

차마 해설보기는 싫고 그래서 질문을 뒤졌다 ..
거기서 힌트를 얻었다. (그게 그건가?)
아무튼 모르겠고 코드는 직접 짰다.
갑자기 뭔가 술술 풀리는 이상한 경험을 했다. 분명 술은 안마셨는데?
싸피에서 배운 백트래킹 그대로 했을뿐 ,,
뇌가 시키는대로 코드를 작성하고 통과하자
갑자기 뭔가 트이는 느낌이 들었다.

풀고나서 해설을 보니 조금 다른데 연구를 한번 해봐야겠다.

근데 잠깐만 내 코드 백트래킹 맞아 ?,, 뭔가 완탐같은데,,,

import java.util.*;

public class Main {
	public static int N, M, K, max, map[][];
	public static int[] dr = {-1,0,1,0};
	public static int[] dc = {0,1,0,-1};
	public static boolean visited[][], grid[][];
	public static Node[] pick, start;
	public static ArrayList<Node> stones = new ArrayList<>();
	public static Queue<Node> q = new LinkedList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
		//맵 크기
		N = sc.nextInt();
		//시작점 수
		M = sc.nextInt();
		//치울 수 있는 돌의 갯수
		K = sc.nextInt();
		pick = new Node[K];
		start = new Node[M];
		visited = new boolean[N][N];
		//맵 입력받기
		map = new int[N][N];
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				map[i][j] = sc.nextInt();
				if(map[i][j]==1){
					stones.add(new Node(i,j));
				}
			}
		}

		for(int i=0;i<M;i++){
			int a = sc.nextInt();
			int b = sc.nextInt();
			start[i] = new Node(a-1,b-1);
		}
		powerSet(0,0);
		System.out.println(max);
    }

	public static void powerSet(int x,int d){
		if(d == K){
			visited = new boolean[N][N];
			grid = new boolean[N][N];
			for(Node n : pick){
				grid[n.x][n.y] = true;
			}
			start();
			BFS();
			return;
		} else if (x == stones.size()){
			return;
		}
		Node now = stones.get(x);
		
		pick[d] = now;
		powerSet(x+1,d+1);

		powerSet(x+1,d);
		
	}
	public static void start(){
		for(Node n : start){
			visited[n.x][n.y] = true;
			q.add(n);
		}
	}


	public static void push(int x,int y){
		if(visited[x][y]){return;}
		visited[x][y] = true;
		q.add(new Node(x,y));
	}

	public static void BFS(){
		int cnt = 0;
		while(!q.isEmpty()){
			Node now = q.poll();
			cnt++;
			for(int d=0;d<4;d++){
				int nx = now.x + dr[d];
				int ny = now.y + dc[d];
				if(canGo(nx,ny)){
					push(nx,ny);
				}
			}
		}
		max = Math.max(cnt,max);
	}

	public static boolean isRange(int x,int y){
		return 0 <= x && x < N && 0 <= y && y < N;
	}

	public static boolean canGo(int x,int y){
		if(!isRange(x,y)) return false;
		else if(grid[x][y]){return true;}
		else if(visited[x][y] || map[x][y]==1) {
			return false;
			}
		return true;
	}

	static class Node{
		int x,y;
		public Node(int x,int y){
			this.x = x;
			this.y = y;
		}
		@Override
		public String toString(){
			return "[ Node x =" + this.x + " y = " + this.y+" ]";
		}
	}
}