[문제풀이] 리틀 프렌즈 사천성

업데이트:

문제 링크 : 리틀 프렌즈 사천성

풀이 시간 : 50분

1. 문제 풀이

일반 사천성 게임과 비슷한 문제

다른 점은 기존 사천성은 선 3개 이하로 연결했다면 이 문제는 2개 이하로만 연결 가능

모든 블록을 제거하면 제거한 순으로 알파벳 출력

방법이 여러개일 경우 알파벳 순으로 가장 먼저인 방법 출력

1) 각 알파벳 블록들의 위치 저장

2) 알파벳 순으로 리스트에 저장하여 하나씩 가능 여부 체크

2-1) 연결이 가능한 경우, 현재 블록 제거 및 알파벳 저장 후 임시 리스트(temp)에 q에 있는 나머지 블록들 저장

2-2) 불가능한 경우, 임시 리스트(temp)에 현재 블록 저장

3) 제거한 블록이 유무 체크

3-1) 있을 경우, 임시 리스트(temp)의 값을 q에 복사 후 2)번으로 이동

3-2) 없을 경우, IMPOSSIBLE 출력

임시 리스트(temp)를 이용하여 q에서 알파벳의 순서를 유지하게 만듬

2. 소스 코드

    public String solution(int m, int n, String[] board) {
		// 알파벳 블록 저장
		Block[] block = new Block[27];
		int[][] map = new int[m][n];
		char c = 'A';
		for (int i = 1; i < block.length; i++) {
			block[i] = new Block(c);
			c++;
		}
		LinkedList<Block> q = new LinkedList<>();
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (board[i].charAt(j) == '.') {
					continue;
				} else if (board[i].charAt(j) == '*') {
					map[i][j] = -1;
				} else {
					int idx = board[i].charAt(j) - 'A' + 1;
					map[i][j] = idx;
					// 처음 만나는 블록인지 확인
					if (block[idx].check) {
						// 두 번째 일 경우 좌표 값 중 왼쪽에 있는 것을 (y1,x1)으로 변경
						if (j > block[idx].x1) {
							block[idx].y2 = i;
							block[idx].x2 = j;
						} else {
							block[idx].y2 = block[idx].y1;
							block[idx].y1 = i;
							block[idx].x2 = block[idx].x1;
							block[idx].x1 = j;
						}
					} else {
						block[idx].y1 = i;
						block[idx].x1 = j;
						block[idx].check = true;
					}
				}
			}
		}
		// 실제로 board에 있는 블록들 저장
		// 알파벳 순서로 저장
		for (int i = 1; i < block.length; i++) {
			if (block[i].check) {
				q.add(block[i]);
			}
		}
		// 결과값
		StringBuilder sb = new StringBuilder();
		LinkedList<Block> temp = new LinkedList<>();
		while (!q.isEmpty()) {
			int size = q.size();
			temp.clear();
			while(!q.isEmpty()) {
				Block b = q.poll();
				boolean flag = true;
				int idx = b.c - 'A' + 1;
				// (y1, x1) 기준으로 (y1, x2)로 갈 수 있는지 체크
				for (int j = b.x1; j <= b.x2; j++) {
					if (map[b.y1][j] == 0 || map[b.y1][j] == idx) {
						continue;
					} else {
						flag = false;
						break;
					}
				}
				// 가능하면
				if (flag) {
					int maxY = Math.max(b.y1, b.y2);
					int minY = Math.min(b.y1, b.y2);
					//  (minY, x2) 기준으로 (maxY, x2) 가능한지 판단
					for (int j = minY; j <= maxY; j++) {
						if (map[j][b.x2] == 0 || map[j][b.x2] == idx) {
							continue;
						} else {
							flag = false;
							break;
						}
					}
					// 가능하면 저장
					if (flag) {
						map[b.y1][b.x1] = 0;
						map[b.y2][b.x2] = 0;
						sb.append(b.c);
						// 나머지는 다시 temp로 이동
						while(!q.isEmpty()) {
							temp.add(q.poll());
						}
						break;
					}
				}
				// 위 조건이 안될 경우
				if (!flag) {
					flag = true;
					int maxY = Math.max(b.y1, b.y2);
					int minY = Math.min(b.y1, b.y2);
					// (minY, x1) 기준으로 (maxY, x1)으로 갈 수 있는지 체크
					for (int j = minY; j <= maxY; j++) {
						if (map[j][b.x1] == 0 || map[j][b.x1] == idx) {
							continue;
						} else {
							flag = false;
							temp.add(b);
							break;
						}
					}
					// 가능한 경우
					if (flag) {
						// (y2, x1) 기준으로 (y2,x2) 갈 수 있는지 체크
						for (int j = b.x1; j <= b.x2; j++) {
							if (map[b.y2][j] == 0 || map[b.y2][j] == idx) {
								continue;
							} else {
								flag = false;
								temp.add(b);
								break;
							}
						}
						// 가능하면 q에 있는 값은 temp 이동
						if (flag) {
							map[b.y1][b.x1] = 0;
							map[b.y2][b.x2] = 0;
							sb.append(b.c);
							while(!q.isEmpty()) {
								temp.add(q.poll());
							}
							break;
						}
					}
				}
			}
			// 아까 q의 사이즈와 temp의 사이즈가 같으면 제거한 블록이 없음
			if (size == temp.size()) {
				return "IMPOSSIBLE";
			}
			// 그러치 않으면 temp를 q에 복사
			q.addAll(temp);
		}
		return sb.toString();
	}

3. 후기

카카오 블라인드 채용이 올라왔다.

준비를 위해서 프로그래머스에 있는 카카오 관련 문제를 다 풀 예정

4. 주의

n = 3, m = 3, board = {“DBF”, “G*F”, “GDB”} 일 경우 답은 “FBGD”

통과가 안됨면 이 테스트 해보기

1) F, G 가능, F가 알파벳 순으로 먼저 이기 때문에 F 제거

2) G, B(F가 제거되어서 가능) 가능, B가 알파벳 순으로 먼저 이기 때문에 B 제거

3) G만 가능 G 제거

4) D만 가능 D 제거

참고