jprogrammers.co.kr/learn/courses/30/lessons/1836?language=java
문제 설명
리틀 프렌즈 사천성
언제나 맛있는 음식들이 가득한 평화로운 푸드 타운. 푸드 타운에서 행복하게 사는 리틀 프렌즈들은 마을에 있는 매직 스푼을 보물처럼 보관하고 있다. 매직 스푼은 재료만 준비해서 냄비에 넣고 휘젓기만 하면 순식간에 최고의 요리로 만들어주는 신비의 아이템. 어느 날 매직 스푼을 호시탐탐 노리는 악당들이 보물을 훔쳐간다. 매직 스푼을 되찾고 다시 마을에 평화를 가져오기 위해 프렌즈의 대모험이 시작되는데...
리틀 프렌즈 사천성은 프렌즈 사천성과 유사한 게임이다. 게임은 2차원 배열에서 진행되는데, 여러 가지 무늬로 구성된 타일이 배치되어 있으며 같은 모양의 타일은 두 개씩 배치되어 있다. 게임의 목적은 배치된 모든 타일을 제거하는 것으로, 같은 모양의 타일을 규칙에 따라 제거하면 된다. 타일을 제거할 수 있는 경우는 다음과 같다.
다음 조건을 만족하는 경로가 있을 때 두 타일을 제거할 수 있다.
- 경로의 양 끝은 제거하려는 두 타일이다.
- 경로는 두 개 이하의 수평/수직 선분으로 구성되어 있고, 이들은 모두 연결되어 있다. (즉, 경로를 한 번 이하로 꺾을 수 있다)
- 참고: 프렌즈 사천성은 경로가 세 개 이하의 선분으로 구성되어야 한다는 점이 다르다. (즉, 경로를 두 번 이하로 꺾을 수 있다)
- 경로 상에는 다른 타일 또는 장애물이 없어야 한다.
위의 배열에서 어피치 타일은 직선의 경로로 이을 수 있으므로 제거 가능하다. 라이언 타일 역시 한 번 꺾인 경로로 연결되므로 제거 가능하다. 무지 타일의 경우 다른 타일을 지나지 않는 경로는 두 번 꺾여야 하므로 제거할 수 없는 타일이며, 튜브 타일 역시 직선의 경로 사이에 장애물이 있으므로 제거 가능하지 않다.
타일 배열이 주어졌을 때, 규칙에 따라 타일을 모두 제거할 수 있는지, 그 경우 어떤 순서로 타일을 제거하면 되는지 구하는 프로그램을 작성해보자.
입력 형식
입력은 게임판의 크기를 나타내는 m과 n, 그리고 배치된 타일의 정보를 담은 문자열 배열 board로 주어진다. 이 배열의 크기는 m이며, 각각의 원소는 n글자의 문자열로 구성되어 있다. 입력되는 값의 제한조건은 다음과 같다.
- 1 <= m, n <= 100
- board의 원소는 아래 나열된 문자로 구성된 문자열이다. 각 문자의 의미는 다음과 같다.
- .: 빈칸을 나타낸다.
- *: 막힌 칸을 나타낸다.
- 알파벳 대문자(A-Z): 타일을 나타낸다. 이 문제에서, 같은 글자로 이루어진 타일은 한 테스트 케이스에 항상 두 개씩만 존재한다.
- board에는 알파벳 대문자가 항상 존재한다. 즉, 타일이 없는 입력은 주어지지 않는다.
출력 형식
해가 존재하는 경우 타일을 제거하는 순서대로 한 글자씩 이루어진 문자열을, 그렇지 않은 경우 IMPOSSIBLE을 리턴한다. 해가 여러 가지인 경우, 알파벳 순으로 가장 먼저인 문자열을 리턴한다.
예제 입출력
mnboardanswer
| 3 | 3 | [DBA, C*A, CDB] | ABCD |
| 2 | 4 | [NRYN, ARYA] | RYAN |
| 4 | 4 | [.ZI., M.**, MZU., .IU.] | MUZI |
| 2 | 2 | [AB, BA] | IMPOSSIBLE |
예제에 대한 설명
첫 번째 테스트 케이스에서 처음으로 제거 가능한 타일은 A와 C이다. 그리고 모든 가능한 경우를 나열하면 ABCD, ACBD, ACDB, CABD, CADB, CDAB이다. 이 중 알파벳 순으로 가장 먼저인 ABCD가 정답이다.
네 번째 테스트 케이스는 초기 상태에서 제거할 수 있는 타일이 없으므로 타일을 모두 제거하는 것이 불가능하다. 따라서 정답은 IMPOSSIBLE이다.
풀이 코드
import java.util.*;
class Solution {
public String solution(int m, int n, String[] board) {
char[][] arr = new char[m][n];
for(int i = 0; i< m; i++){
arr[i] = board[i].toCharArray();
}
ArrayList<Character> al = new ArrayList<Character>();
for(int i =0 ; i< m ; i++){
for(int j =0; j< n; j++){
if(arr[i][j]!='.'&& arr[i][j]!='*' && !al.contains(arr[i][j]))al.add(arr[i][j]);
}
}
Collections.sort(al);
StringBuilder ans = new StringBuilder();
for(int a = 0; a<al.size();a++){
char C = al.get(a);
loop:
for(int I = 0; I< m; I++){
for(int J = 0; J<n; J++){
if(arr[I][J]==C){//만약 같으면 bfs로 한번 꺽으면서, 가능한거 찾기
//상하좌우,1,2,3,4//사실 근데 상은 필요없다.
Queue<int[]> q = new LinkedList<int[]>();
q.add(new int[]{I,J,2,0});//new int[4]; //i, j, d, cnt (위치, 방향, 꺾은 수 )
q.add(new int[]{I,J,3,0});//new int[4]; //i, j, d, cnt (위치, 방향, 꺾은 수 )
q.add(new int[]{I,J,4,0});//new int[4]; //i, j, d, cnt (위치, 방향, 꺾은 수 )
while(!q.isEmpty()){// q에 암것도 없지 않을 때까지
int[] t = q.poll();
int i = t[0];int j = t[1]; int d = t[2];
//하
if(i<m-1 && !(i+1==I && j==J) && d==2){ //우선 만약 같은 방향이면,
if(arr[i+1][j]==C){ //같은 값이면?
arr[I][J] = '.';arr[i+1][j]='.'; //그 위치 비워주고,
ans.append(C);//ans에 값 붙여주고,
al.remove(a); a=-1;//al지우고, 첨부터 시작
break loop;
}else if(arr[i+1][j]=='.'){// 그렇지 않고 만약 지나갈 수 있으면,
q.add(new int[]{i+1,j,2,t[3]}); //q에 넣기
}
}else if(i<m-1 && !(i+1==I && j==J) && t[3]==0 ){ // 다른방향이고,꺾을 수 있다면,
if(arr[i+1][j]==C){ //같은 값이면?
arr[I][J] = '.';arr[i+1][j]='.'; //그 위치 비워주고,
ans.append(C);//ans에 값 붙여주고,
al.remove(a); a=-1;//al지우고, 첨부터 시작
break loop;
}else if(arr[i+1][j]=='.'){// 그렇지 않고 만약 지나갈 수 있으면,
q.add(new int[]{i+1,j,2,1}); //q에 넣기
}
}
//좌
if(j>0 && !(i==I && j-1==J) && d==3){ //우선 만약 같은 방향이면,
if(arr[i][j-1]==C){ //같은 값이면?
arr[I][J] = '.';arr[i][j-1]='.'; //그 위치 비워주고,
ans.append(C);//ans에 값 붙여주고,
al.remove(a); a=-1;//al지우고, 첨부터 시작
break loop;
}else if(arr[i][j-1]=='.'){// 그렇지 않고 만약 지나갈 수 있으면,
q.add(new int[]{i,j-1,3,t[3]}); //q에 넣기
}
}else if(j>0 && !(i==I && j-1==J) &&t[3]==0 ){ // 다른방향이고,꺾을 수 있다면,
if(arr[i][j-1]==C){ //같은 값이면?
arr[I][J] = '.';arr[i][j-1]='.'; //그 위치 비워주고,
ans.append(C);//ans에 값 붙여주고,
al.remove(a); a=-1;//al지우고, 첨부터 시작
break loop;
}else if(arr[i][j-1]=='.'){// 그렇지 않고 만약 지나갈 수 있으면,
q.add(new int[]{i,j-1,3,1}); //q에 넣기
}
}//우
if(j<n-1&& !(i==I && j+1==J) && d==4){ //우선 만약 같은 방향이면,
if(arr[i][j+1]==C){ //같은 값이면?
arr[I][J] = '.';arr[i][j+1]='.'; //그 위치 비워주고,
ans.append(C);//ans에 값 붙여주고,
al.remove(a); a=-1;//al지우고, 첨부터 시작
break loop;
}else if(arr[i][j+1]=='.'){// 그렇지 않고 만약 지나갈 수 있으면,
q.add(new int[]{i,j+1,4,t[3]}); //q에 넣기
}
}else if(j<n-1&& !(i==I && j+1==J) && t[3]==0 ){ // 다른방향이고,꺾을 수 있다면,
if(arr[i][j+1]==C){ //같은 값이면?
arr[I][J] = '.';arr[i][j+1]='.'; //그 위치 비워주고,
ans.append(C);//ans에 값 붙여주고,
al.remove(a); a=-1;//al지우고, 첨부터 시작
break loop;
}else if(arr[i][j+1]=='.'){// 그렇지 않고 만약 지나갈 수 있으면,
q.add(new int[]{i,j+1,4,1}); //q에 넣기
}
}
}
}
}
}
}
return al.size()!=0?"IMPOSSIBLE":ans.toString();
}
}
코드 풀이
푸는 방법을 요약하자면,
1. 현재 board에 포함된 문자들을 찾고 개수도 센다
2. 알파벳순으로 정렬하므로 찾은 문자들을 정렬하고, 제일 앞 문자부터 문자들을 넣은 al을 순회하면서 없앨 수 있는 것들을 모두 없앤다.
3. 없애는 방법은 Queue에 넣어 bfs를 돈다. 만약 한번 꺽고, 없애기가 가능하면, 그 자리를 '.'로 채우고, 다시 반복해서 돌던 al의 0으로 가서 다시 탐색한다.
4. al에 남아있는 문자가 0이 아니라면 다 순회하지 못한 것이므로 "impossible""아니면 StringBuilder에 담았던 값 리턴
그럼 이렇게 적은 코드를 보면,
먼저 board가 string으로 되어 있으므로 character로 바꿔준다.
그리고 ArrayList인 al을 선언해 주고,
반복문을 돌면서 문자이면서 이전 al에 포함되지 않았다면 al에 포함시킨다.
그리고는 al을 정렬하여 알바펫 오름차순으로 정렬되게 한다.
없어지는 순서에 따른 답을 담을 StringBuilder ans를 선언해주고,
al을 반복하게 된다.
al을 너무 많이 불러오면 번거로우니 char C로 담아준다.
그리고 이후 반복문을 돌면서, 가장 왼쪽 상단에 나오는 가장 문자가 빠른 값을 찾아준다.
만약에 값을 찾으면 그 이후로는 상하좌우 중에 하좌우만 찾으면 된다.
이제 Queue를 선언하고, 이를 통해서 bfs를 돌게 된다.
Queue에 들어가는 값은, i위치, j위치, 방향, 꺾은 횟수가 된다.
이후 wihile문을 통해 bfs를 도는데,
이후 이어지는 조건이 많기 때문에 i,j,d로 세로 위치, 가로위치, 방향을 따로 담아준다.
그리고 이후로 아래 방향부터 검사하게되는데,
먼저 방향이 같은 경우부터 검사한다.
방향이 같고, i도 끝이 아니라더 내려갈 수 있고, 처음의 위치와 같지도 않다면, 검사를 하는데,
arr[i][j]가 C와 동이라면, 사라질 수 있기 때문에, 그 값을 StringBuilder인 ans에 담아주고, 그 위치는 '.'로 빈칸으로 만들어준다.
그리고 그 값은 사라졌으므로, al에서 a위치에 있는 C값을 지워주고, 알파벳순으로 이루어져야 하기 떄문에, a를 -1로 만들어 다시 al.get(0)부터 반복할 수 있게 한다.
그리고 방향이 다르다면 조건문을 진행하는데, 방향이 다르고 t[3]=0이어서 꺾은 적이 없는 경우만 가능하다.
이후 코드는 이전에 같은방향이었을 때와 동일한데,
arr[i][j]='.'로 갈 수 있다면, 이제 q에 들어가는 꺾은 횟수가 1로 변하는 것이 달라지게 된다.
이러한 방법으로 하/좌/우를 모두 순회하게된다.
다 반복한 이후, 조건에 따라서 al.size() 즉 다 순회해도 남아있는 문자가 있다면 "IMPOSSIBLE"아니라면 StringB:uilder에 담아뒀던 닶을 String형태로 바꿔 return 해주면 된다.
'코딩테스트 연습 > 프로그래머스' 카테고리의 다른 글
| [ 코딩테스트연습 / 프로그래머스 ] lv2 할인행사 java (0) | 2023.08.14 |
|---|---|
| [프로그래머스] 거리두기 확인하기 Java (0) | 2021.07.29 |
| [ 프로그래머스 > 월간 코드 챌린지 시즌1 ]LEVEL 2 : 쿼드압축 후 개수 세기, solved by java (0) | 2020.10.27 |
| [ 프로그래머스 / 월간 코드 챌린지 시즌1] LEVEL 2 - 삼각 달팽이 : solved by Java (0) | 2020.10.25 |
| [프로그래머스 ] level2 - 방금그곡; solved by JAVA (1) | 2020.10.24 |
