codingtest

리틀 프렌즈 사천성

2025-10-19
3분 분량
JAVA프로그래머스

문제 링크

문제 풀이 시간 : 1시간 53분

문제 요약

  • 보드는 m × n 크기의 문자 격자.
  • 각 알파벳 대문자는 정확히 2개 존재(쌍).
  • 두 같은 알파벳은 직선으로 연결되거나 한 번만 꺾어서(L자) 연결될 수 있어야 제거 가능.
  • 경로는 .(빈칸)은 통과 가능, *(장애물)이나 다른 알파벳은 통과 불가.
  • 매 라운드에서 사전순으로 제거 가능한 타일을 찾아 제거. 제거 가능한 문자가 하나도 없으면 "IMPOSSIBLE"

문제 풀이

잘못된 시도

이 문제를 처음 봤을 때는 어떤 순서로 타일을 지워야 할지 전혀 감이 오지 않았다.

처음에는 순차적으로 보드를 탐색하면서, 삭제할 수 있는 문자를 우선순위 큐에 넣는 방식으로 접근했다.

하지만 이 방법으로는 보드 상태가 바뀌는 시점에 따라 알파벳 순서가 꼬이는 문제가 발생했다.

즉, 우선순위 큐가 있다고 해도 이미 제거된 타일이 열어준 경로를 다시 반영하기 어려워서 결국 알파벳 순서대로 처리가 되지 않는 경우가 생겼다.

정답 시도

그래서 생각을 바꿔, 사전순으로 알파벳을 고정한 뒤,

각 문자가 “지울 수 있는 상태인지”를 반복적으로 확인하는 방식으로 바꾸었다.

즉,

  1. 처음에 보드를 전부 스캔해서 각 알파벳의 위치 두 개를 저장하고,
  2. 알파벳들을 정렬하여 리스트에 담은 다음,
  3. 사전순으로 하나씩 “지울 수 있는지” 검사한다.
  4. 지울 수 있으면 바로 보드에서 두 칸을 .로 바꾸고 다시 처음부터 탐색을 반복한다.

이 과정을 반복하다가 한 번도 제거가 되지 않으면 "IMPOSSIBLE"을 반환한다.

연결 판단 로직

연결은 직선 또는 한 번 꺾는 경로만 허용된다.

  • 직선 연결
  • 한 번 꺾는 연결 (L자 경로)
java
//세로 방향에 다른 문자가 없는지 확인
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로 탐색하려고 했지만 보드 크기가 작고 알파벳 개수가 많지 않기 때문에 각 알파벳 쌍을 직접 검사하는 방식이 훨씬 단순하고 빠르다.

또한 사전순으로 제거하기 때문에 한 번이라도 지울 수 있는 문자가 있으면 그 문자를 먼저 지우고 다시 처음부터 탐색을 반복해야 한다.

최종 코드

java
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();
    }
}

함께 읽으면 좋은 글

코딩 테스트2026-08-23

택배상자

order 배열은 택배 기사님이 원하는 상자 적재 순서다 기존 컨테이너 벨트는 1번부터 순서대로만 꺼낼 수 있다 보조 벨트는 스택처럼 마지막에 넣은 것부터 꺼낼 수 있다 원하는 순서대로 최대한 실을 수 있는 상자 개수를 구하는 문제다 처음에는 기존 벨트를 실제 리스트로 만들어…

코딩 테스트2026-08-23

롤케이크 자르기

topping 배열은 롤케이크에 일렬로 올라간 토핑 번호다 한 지점을 잘라 두 조각으로 나눴을 때, 양쪽 토핑 종류 수가 같아야 공평하게 나눈 것이다 공평하게 자를 수 있는 방법의 수를 구하는 문제다 처음에는 자르는 위치마다 왼쪽과 오른쪽 배열을 나눠서 각각 서로 다른 토핑…

코딩 테스트2026-08-23

할인 행사

want, number 배열로 정현이가 원하는 제품과 수량을 표현한다 discount 배열은 XYZ 마트가 매일 할인하는 제품 목록이다 연속된 10일 동안 할인 제품 종류와 수량이 want, number와 정확히 일치해야 회원가입할 수 있다 그런 시작일이 총 몇 번 있는지…

코딩 테스트2026-08-23

숫자 변환하기

자연수 x를 y로 바꾸는 데 x+n, x2, x3 세 가지 연산을 쓸 수 있다 x를 y로 바꾸는 최소 연산 횟수를 구하는 문제다 만들 수 없으면 -1을 반환한다 처음에는 x에서 시작해서 세 가지 연산을 재귀적으로 다 시도해보고 y에 도달하는 경로 중 가장 짧은 걸 고르면…

← 서재 목록으로 돌아가기