벽돌 깨기

문제 접근 방법

  • W개 열 중에서 N개 선택하는 순열을 생성하여 N개 열 선택하고 나면 N개의 시작점(x,y)에서 Map[x][y]-1만큼 DFS로 벽돌 부수는 탐색한다. (시작점=N개의 열에서 0보다 큰 숫자가 처음 나오는 위치)

  • 탐색이 끝나고 난 후, 그 때마다 남아있는 벽돌 갯수 카운팅해야하는데 탐색을 진행하면서 부순 벽돌 갯수를 합산하거나 남은 벽돌 갯수 감산할 수 있는지, 혹은 다 부순 후에 벽돌 갯수 카운팅하는 부분을 따로 구현해야하는지 판단이 서지 않아 이 부분은 결국 구현도 못 했다. 정답 코드를 보니 벽돌 다 부순 후에 따로 벽돌 갯수 세는 것 같다.

  1. 순열 생성 메서드 permu(int index,int selected) : W개 열 중 N개 선택하는 순열 만드는 메서드 permu : N개 다 선택하면 폭발 시작할 지점에서 DFS + 그 때의 남은 벽돌 갯수 카운팅해서 정답 변수 ans에 갱신, 저장하는 것까지 포함되야함...

  2. findStart : DFS 시작하는 N개 시작점 위치 찾는다.

  3. dfs(int x,int y) : (x,y)에서 DFS 시작.

처음 생각=>순열 생성 메서드 정답 찾은 경우 무엇을 실행해야하는지⭐️ 순열 생성할 때 N개 다 선택한 경우, DFS 진행하려고 했다. 하지만 DFS 진행하려면 먼저, 시작점을 찾아야하기 때문에 findStart가 선행되어야한다. 그래서 N개 다 선택한 후에 DFS 시작점 찾는 findStart만 호출하고 리턴해버렸다. =>원래 생각했던 대로, N개 다 선택한 경우, DFS 진행하면된다. DFS함에 따라서 그 때의 남은 벽돌 세주고, 최솟값으로 정답 갱신&저장해주면 되는 것이였다. 아직 구현 자신감이 부족한 것인가..

구현에 있어서 신경써야할 것들 순열을 생성하여, 각 순열=각 경우마다 2차원 배열의 값을 계속 변경하기 때문에 한 경우가 끝나고 난 후, 2차원 배열을 복원시켜야한다. 이 때 복원하는 시점과 코드 내 장소를 생각해봤다. =>일단 N개 순열 만들고 나면, 선택한 열j를 저장하는 1차원 배열만 생각했다. 그래서 N개 순열 만들고 나면 그 때 DFS가 진행되고, 선택한 열j를 저장하는 배열은 열 선택과 함께 배열에 덮어쓰는 형태로 선택&저장되기 때문에 선택한 열 저장하는 1차원 배열은 따로 원복할 필요 없다고 생각했다. 2차원 배열 복원은 어떻게 처리했나? 1차원 배열만 생각하고 2차원 배열은 생각만 하고, 깜빡하고(?) 구현 안/못 한 것 같다.

부족한 부분 문제 푸는 데에 필요한 로직들은 모두 생각했지만,로직을 코드로 꼼꼼하게 유기적으로 구현해내는 능력. 자유자재로 순열 생성하고 2차원 배열 탐색.

내가 생각했던 로직들이 그대로 일대일 대응되게 있었다. 다만 내가 참고한 코드에서는 탐색을 BFS로 하나의 방향에 대해 계속해서 동일한 방향으로 Map[x][y]만큼 진행되도록 코드를 구현했다.

순열 생성 메서드에서 N개 다 선택하고 난 후, 디테일하게 실제로 어떻게 구현되나? 1. 현재 배열 복사해서 배열 하나 더 생성 2. 벽돌깨기 3. 남은 벽돌 갯수 카운팅, ans 갱신 

  1. private static void makeSet(int spot) {
		if (spot == N) {
			// 벽돌 선별 및 부시기
			int[][] copy = copyMap();
			int brick = 0;

			for (int i = 0; i < N; ++i) {
				visited = new boolean[H][W];
				selectAndCresh(copy, spots[i]);
				compact(copy);
			}
			
			brick = count(copy);
			// 현재 남은 벽돌 수와 지금까지 가장 적게 남은 벽돌수를 비교해 ans 갱신
			ans = ans > brick ? brick : ans;

			return;
		}

		for (int w = 0; w < W; ++w) {
			spots[spot] = w;
			makeSet(spot + 1);
		}
	}

    내 문제 풀이, 접근 방식과 가장 유사한 방식은 BFS 솔류션이였다. DFS도 방법은 달랐지만(각 행,열을 선택하고 바로 탐색) 결국 탐색하는 부분만 조금 달랐다.

전체 코드 골격은 동일하다. 탐색하는 부분만 BFS/DFS 다르게 구현해주면 될 것 같다. BFS(순열 관점)로 먼저 짜보기. - 순열 관점, 선택 관점.

위에서부터 순서대로 BFS, DFS 실행 결과다. 시간은 약 10배차이 나고, 메모리는 약 3-4배 정도 차이 난다. DFS문제라는 걸 직감하고 풀었지만, 이렇게 시간/메모리 차이가 난다는 것이 놀라웠다. DFS는 깊이 우선으로 진행하다가 아니다 싶으면? 조건 불만족하면 바로 백하는데 반해 BFS는 현재 시작 시점 기준으로 인접한 모든 노드를 방문하기 때문?

BFS 시간/메모리 줄이기 선택 관점 ① 불가능한 경우 selected>N : 불필요한 백트랙킹🔺 정답 찾은 경우, index == N이 될 때 리턴하기 때문에 index>N이 되는 경우는 없다! num>=W ✅ ② 정답 찾은 경우 ③ 현재 선택하고 다음 경우 호출

선택 관점에서 열을 선택하는 코드 > 틀린 이유 : N=3,W=10일 때, 10개 중에서 3개의 열을 선택해야한다. 선택한 열들을 저장하는 spots 배열에서 현재 열을 선택하여 저장하는인덱스를 selected라고 하고, W 중에서 0부터 시작하는 인덱스를 index라고 한다. 따라서 index의 범위는 의심의 여지 없이 0부터 W-1까지이고, selected가 관건이다. 일단 spots 배열의 크기는 N=3이 된다.

아래 코드가 틀린 이유는 선택하는 열j가 W개의 숫자가 나오는 것이 아니라, 0부터 3-1까지 나온다.왜ㅗ냐하면 selected가 N을 초과하면 리턴하도록 되어있기 때문이다.

그런데 선택하는 수는 W만큼 들어가야한다. 배열의 인덱스 selected는 0~N-1까지이지만, 현재 배열의 인덱스 selected에서 앞에 선택한 수들을 제외한 수를 넣어야한다. =>원인을 찾지 못한 채(?) 해결함.

private static void makeSet(int index,int selected) {//index:W에서 선택할 인덱스,selected:현재까지 선택한 인덱스
		if(selected>N)return;
		if(index>=W) return;
		if(selected == N) {
			System.out.print("선택한 열j 순열: ");
			for(int i=0;i<N;i++) {
				System.out.print(spots[i]+" ");
			}
			System.out.println();
			//BFS 호출,벽돌 카운팅,정답 갱신 로직
			return;
		}
		
		spots[selected] = index;
		makeSet(selected+1,index+1);
		spots[selected] = 0;
		makeSet(selected,index+1);
	}

수정한 선택한 관점.W개 중에서 N개 선택한 코드 

private static void makeSet(int index,int num) {//index:W에서 선택할 인덱스,selected:현재까지 선택한 인덱스
		if(index == N) {
			System.out.print("선택한 열j 순열: ");
			for(int i=0;i<N;i++) {
				System.out.print(spots[i]+" ");
			}
			System.out.println();
		//BFS 호출,벽돌 카운팅,정답 갱신 로직
			return;
	
		}
		if(num>=W) return;
		
		spots[index] = num;
		makeSet(index+1,num+1);
		spots[index] = 0;
		makeSet(index,num+1);
	}

전혀 달라진 코드 없이 순열 만드는 부분만 바꿨더니 오답이 나온다. 순열을 출력해보니 정답코드는 중복을 허용하는 순열을 만드는 것이였다.

따라서, 순열을 만들 때, 중복 순열을 만드는 로직이 들어가야한다. 그런데 선택관점으로 중복 순열을 선택할 수 있는지 의문점이 발생한다. 중복 순열은 index+1에도 동일한 num이 들어갈 수 있다.

선택O spots[index] = num; permu(index+1,num); permu(index+1,num+1); permu(index+1,num+2); ...

선택X spots[index] = 0; permu(index,num); permu(index,num+1); permu(index,num+2); ...

중복을 허용하지 않는 순열을 만들 때는 선택관점에서 순열을 만들 수 있지만(반복문 없이 2번의 재귀호출), 중복을 허용하는 경우, 다음에 올 숫자는 num+1부터가 아니라 num부터 num+1,num+2,.. 모두 가능하기 때문에 이 부분은 반복문으로 구현하는 것이 바람직하다

W개 중에서 N개를 선택하여 만드는 중복 순열 코드: 000~999까지 모든 순열을 만든다.

private static void makeSet(int index) {
		if(index == N) {...}
		for(int i=0;i<W;i++) {
			spots[index] = i;
			makeSet(index+1);
		}
	}

따라서 BFS코드에서 중복순열을 만드는 로직에서 개선할 부분은 없는 것 같고, BFS 탐색 로직 또한, 인접한 상하좌우 칸들을 모두 큐에 넣어서 탐색하기 때문에 조건에 만족하지 않으면 바로 리턴하는 DFS와 성능 차이가 날 수 밖에 없는 듯하다. 정 DFS 코드(현재 참고한 코드)를 이해하기 힘들면 BFS코드로 연마해야겠지만...

2번째 DFS 참고 소스

아래 로직을 N번 반복하면 다.

  • 벽돌 부수기

  • 벽돌 내리기

  1. dfs(int[ ][ ] arr, int cnt) : cnt는 현재 구슬 갯수를 의미하며 0~N-1까지이다. N개를 모두 쐈을 때, cnt == N이 되면 구슬 모두 쐈으므로 남은 벽돌 갯수 세서 정답 최솟값 갱신한다. (문제)행이 H라고 하면 맨 윗칸에 구슬을 쏨으로써 맨 윗칸의 벽돌 1개가 부서지고, 벽돌 숫자만큼 인접한 벽돌들 부서진다. dfs함수 ① 현재 j번 에서 구슬을 1개씩 쏴서 벽돌 1개씩 없앤다. ② crash함수 호출하여 인접 벽돌 처리 ③ dfs재귀호출하여 cnt+1번째 구슬도 쏜다. ④ 없앤 벽돌 다시 +1 증가시켜서 원복

  2. crash(int[ ][ ] dup,int spot) : 인접한 벽돌 부수기 : 큐를 이용하여 진행하고, BFS와 거의 동일. spot열에서 벽돌 부수는 시작점(맨윗행)을 찾아서 큐에 넣고, 인접한 노드 BFS처럼 탐색해서 부순다.(재귀함수❌) 큐가 빌 때까지 탐색해서 벽돌 다 부수고 나면 벽돌 내리는 부분도 함께 포함한다.

  3. 백트랙킹 : 입력받을 때 벽돌(0보다 큰 수) 갯수를 sum에 저장한다. sum : 벽돌 갯수, num = 구슬 갯수. sum은 양수인 칸의 갯수를 의미한다. 즉, sum개를 제외한 나머지 모든 칸들은 0이라는 의미이다. 따라서 sum<=num이 되면 벽돌을 부수는 탐색을 하지 않아도, 구슬 num개를 쏴서 벽돌들을 다 부수고, 우리가 구하고자 하는 남은 벽돌 수는 0이 되므로, 어떠한 함수를 실행하지 않고 바로 정답(=0)을 출력할 수 있다.

// 벽돌을 전부 깰 수 있는 경우
if (sum <= num) {
  System.out.println("#" + t + " " + 0);
  continue;
}

코드를 외우지 말고, 로직을 이해하기. 로직은 이해가 다 되었다. 그런데 아직 잡히지 않았다.

Previous보물 상자 비밀번호Next줄기 세포 배양

Last updated