리틀 프렌즈 사천성
문제 풀이 시간 : 1시간 53분
문제 요약
- •
보드는
m × n크기의 문자 격자.
- •
각 알파벳 대문자는 정확히 2개 존재(쌍).
- •
두 같은 알파벳은 직선으로 연결되거나 한 번만 꺾어서(L자) 연결될 수 있어야 제거 가능.
- •
경로는
.(빈칸)은 통과 가능,*(장애물)이나 다른 알파벳은 통과 불가.
- •
매 라운드에서 사전순으로 제거 가능한 타일을 찾아 제거. 제거 가능한 문자가 하나도 없으면
"IMPOSSIBLE"
문제 풀이
잘못된 시도
이 문제를 처음 봤을 때는 어떤 순서로 타일을 지워야 할지 전혀 감이 오지 않았다.
처음에는 순차적으로 보드를 탐색하면서, 삭제할 수 있는 문자를 우선순위 큐에 넣는 방식으로 접근했다.
하지만 이 방법으로는 보드 상태가 바뀌는 시점에 따라 알파벳 순서가 꼬이는 문제가 발생했다.
즉, 우선순위 큐가 있다고 해도 이미 제거된 타일이 열어준 경로를 다시 반영하기 어려워서 결국 알파벳 순서대로 처리가 되지 않는 경우가 생겼다.
정답 시도
그래서 생각을 바꿔, 사전순으로 알파벳을 고정한 뒤,
각 문자가 “지울 수 있는 상태인지”를 반복적으로 확인하는 방식으로 바꾸었다.
즉,
- 1
처음에 보드를 전부 스캔해서 각 알파벳의 위치 두 개를 저장하고,
- 2
알파벳들을 정렬하여 리스트에 담은 다음,
- 3
사전순으로 하나씩 “지울 수 있는지” 검사한다.
- 4
지울 수 있으면 바로 보드에서 두 칸을
.로 바꾸고 다시 처음부터 탐색을 반복한다.
이 과정을 반복하다가 한 번도 제거가 되지 않으면 "IMPOSSIBLE"을 반환한다.
연결 판단 로직
연결은 직선 또는 한 번 꺾는 경로만 허용된다.
- •
직선 연결
같은 행(x좌표 동일)일 경우 → 가로 방향으로
같은 열(y좌표 동일)일 경우 → 세로 방향으로
사이에 다른 문자가 없어야 연결 가능하다.
이때 양 끝점은 제외하고 사이 칸만 검사해야 한다.
- •
한 번 꺾는 연결 (L자 경로)
두 칸의 코너가 되는 점
(x1, y2)또는(x2, y1)중 하나가.이면,그 코너를 기준으로 두 직선 구간이 모두 비어 있으면 연결 가능하다.
//세로 방향에 다른 문자가 없는지 확인
public boolean isClearCol(int x, int y, int a, int b){
if(x>a){
int t = x;
x = a;
a = t;
}
x++;
for(;x<a;x++){
if(tile[x][y]!='.')
return false;
}
return true;
}
//가로 방향에 다른 문자가 없는지 확인
public boolean isClearRow(int x, int y, int a, int b){
if(y>b){
int t = y;
y = b;
b = t;
}
y++;
for(;y<b;y++){
if(tile[x][y]!='.')
return false;
}
return true;
}
public boolean canConnect(int x, int y, int a, int b){
//직선 연결이 가능한지 확인
if (x==a && isClearRow(x,y,a,b))
return true;
if (y==b && isClearCol(x,y,a,b))
return true;
//한번 꺾는 연결이 가능한지 확인
if(tile[x][b]=='.' && isClearRow(x,y,x,b) && isClearCol(x,b,a,b))
return true;
if(tile[a][y]=='.' && isClearRow(a,y,a,b) && isClearCol(x,y,a,y))
return true;
return false;
}왜 이렇게 해야 할까
처음엔 단순히 BFS나 DFS로 탐색하려고 했지만 보드 크기가 작고 알파벳 개수가 많지 않기 때문에 각 알파벳 쌍을 직접 검사하는 방식이 훨씬 단순하고 빠르다.
또한 사전순으로 제거하기 때문에 한 번이라도 지울 수 있는 문자가 있으면 그 문자를 먼저 지우고 다시 처음부터 탐색을 반복해야 한다.
최종 코드
import java.util.*;
class Solution {
public char[][] tile;
public int m,n;
public boolean isClearCol(int x, int y, int a, int b){
if(x>a){
int t = x;
x = a;
a = t;
}
x++;
for(;x<a;x++){
if(tile[x][y]!='.')
return false;
}
return true;
}
public boolean isClearRow(int x, int y, int a, int b){
if(y>b){
int t = y;
y = b;
b = t;
}
y++;
for(;y<b;y++){
if(tile[x][y]!='.')
return false;
}
return true;
}
public boolean canConnect(int x, int y, int a, int b){
if (x==a && isClearRow(x,y,a,b))
return true;
if (y==b && isClearCol(x,y,a,b))
return true;
if(tile[x][b]=='.' && isClearRow(x,y,x,b) && isClearCol(x,b,a,b))
return true;
if(tile[a][y]=='.' && isClearRow(a,y,a,b) && isClearCol(x,y,a,y))
return true;
return false;
}
public String solution(int m, int n, String[] board) {
this.m = m;
this.n = n;
tile = new char[m][n];
Set<Character> set = new HashSet<>();
Map<Character, List<int[]>> map = new HashMap<>();
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
char now = board[i].charAt(j);
tile[i][j] = now;
if(now >='A' && now<='Z'){
set.add(now);
map.computeIfAbsent(now, k -> new ArrayList<>()).add(new int[]{i,j});
}
}
}
List<Character> letters = new ArrayList<>(set);
Collections.sort(letters);
StringBuilder sb = new StringBuilder();
while(!set.isEmpty()){
boolean isRemove = false;
for(char letter : letters){
List<int[]> now = map.get(letter);
if(!set.contains(letter) || now.size() != 2)
continue;
int[] a = now.get(0);
int[] b = now.get(1);
if(canConnect(a[0],a[1],b[0],b[1])){
tile[a[0]][a[1]] = '.';
tile[b[0]][b[1]] = '.';
set.remove(letter);
sb.append(letter);
isRemove = true;
break;
}
}
if(!isRemove)
return "IMPOSSIBLE";
}
return sb.toString();
}
}