프렌즈4블록

https://programmers.co.kr/learn/courses/30/lessons/17679

코딩테스트 연습 - [1차] 프렌즈4블록 | 프로그래머스

---

카카오의 코딩테스트를 풀면서 한 문제에 여러가지 로직이 들어간다고 생각했습니다. 그래서 한 부분에서 꼬이게 되면 계속 꼬여서 처음부터 풀이를 잘 생각하고 체계적으로 풀어야 하는 것 같습니다. 이번 문제에서도 설명을 따라서 하나하나씩 코드를 실수 없이 풀어가다보면 해결할 수 있었습니다. 저는 어려웠던 부분이 4블록을 찾아 표시하는 것 까지는 했지만, 이제 그 블록들을 없애고 열 단위로 위에서 비어있는 칸에 당겨서 채워가는 부분이 어려웠습니다. 그래서 저는 열이 n개로 주워져있기 때문에 n개의 ArrayList를 만들어서 반복할 때 마다 없앤 칸을 제외하고 ArrayList 에 넣어서 새로운 map을 만들었습니다. 이 부분에서 행과 열의 인덱스를 계산할 때 헷갈리는 부분이 많았습니다. 이것을 해결하고 나서는, 없어지는 블록의 개수를 구하는 부분만 추가해서 반복문을 빠져나오면 풀 수 있는 문제였습니다.

< 문제 풀이 >

1. 주어진 String[] board 배열을 나누어서 char[m][n] 배열에 먼저 넣습니다.

2. 그리고 check 함수를 만들어서 2차원 char 배열을 돌면서 지울 수 있는 4블록을 visited 배열에 true라고 표시 합니다.

3. 여기에서 어떻게 true 라고 있는 visited 배열에 위에서 부터 채울까 생각을 해봤는데, 저는 ArrayList를 열 별로 만들어서 0번째부터 n번째 까지 모든 열을 돌면서 아래서 부터 차례대로 visited 가 false 인 부분을 ArrayList에 넣었습니다.

4. 그리고 나서 다시 map을 생성하는데, ArrayList에 담긴 문자들을 3번과 같이 반복문을 돌면서 map을 채웁니다.

5. 그러면 한번 시행 했을 때 4블록이 없어진 문자들이 map 배열에 갱신이 되게 됩니다.

6. 없어진 블록을 체크하는 것은 ArrayList에 배열을 채우면서 visited가 false 가 아닌 true 인 것을 더해주면 됩니다.

7. 이제 더이상 4블록을 지울게 없어서 while 문을 빠져나오는 방법은 flag 변수를 선언해서, check를 한 후에 visited가 true인 것이 하나도 없게 되면 flag 변수가 그대로 false 이기 때문에 break를 해줍니다.

---

import java.util.ArrayList;

class Solution {
    
    static char[][] map;
	static boolean[][] visited;
	static int a, b;
	static ArrayList<Character>[] line;
  public int solution(int m, int n, String[] board) {
      		int answer = 0;
		a = m;
		b = n;
		map = new char[a][b];

		for (int i = 0; i < board.length; i++) {
			char[] ch = board[i].toCharArray();
			for (int j = 0; j < b; j++) {
				map[i][j] = ch[j];
			}
		}
		
		while(true) {
		
			visited = new boolean[a][b];
			line = new ArrayList[b];
			boolean flag = false;

			for (int i = 0; i < b; i++) {
				line[i] = new ArrayList<Character>();
			}

			// 지워지는 4블록들 표시하기.
			for (int i = 0; i < a - 1; i++) {
				for (int j = 0; j < b - 1; j++) {
					if (map[i][j] == 0)
						continue;
					check(i, j);
				}
			}

			Outter: for (int i = 0; i < a; i++) {
				for (int j = 0; j < b; j++) {
					if (visited[i][j] == true) {
						flag = true;
						break Outter;
					}
				}
			}

			if (!flag) {
				break;
			}

			// 지워지는 4블록들 지우고, 지워진거 빼고 밑에서 부터 위에까지 행 단위로 line에 저장.
			for (int i = 0; i < b; i++) {
				for (int j = a - 1; j >= 0; j--) {
					if (visited[j][i] == false) {
						line[i].add(map[j][i]);
					} else {
						answer++;
					}
				}
			}

			map = new char[a][b];

			// 지워진 배열빼고 다시 char 배열에 저장.
			for (int i = 0; i < b; i++) {
				for (int j = a - 1; j >= 0; j--) {
					if (line[i].size() <= a - 1 - j)
						break;
					map[j][i] = line[i].get((a - 1) - j);
				}
			}
		}
		
		

		return answer;
  }
    public static void check(int x, int y) {
		if (isInside(x, y)) {
			if (map[x][y] == map[x + 1][y] && map[x][y] == map[x][y + 1] && map[x][y] == map[x + 1][y + 1]) {
				visited[x][y] = true;
				visited[x + 1][y] = true;
				visited[x][y + 1] = true;
				visited[x + 1][y + 1] = true;
			}
		}
	}

	public static boolean isInside(int x, int y) {
		if (x >= 0 && y >= 0 && x < a && y < b)
			return true;
		else
			return false;
	}
}