🎯문제
가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다. 네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원했다. 사진을 찍고 나서 돌아오는 길에, 무지는 모두가 원하는 조건을 만족하면서도 다르게 서는 방법이 있지 않았을까 생각해보게 되었다. 각 프렌즈가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해보자.
입력 형식
입력은 조건의 개수를 나타내는 정수 n과 n개의 원소로 구성된 문자열 배열 data로 주어진다. data의 원소는 각 프렌즈가 원하는 조건이 N~F=0과 같은 형태의 문자열로 구성되어 있다. 제한조건은 아래와 같다.
1 <= n <= 100data의 원소는 다섯 글자로 구성된 문자열이다. 각 원소의 조건은 다음과 같다.- 첫 번째 글자와 세 번째 글자는 다음 8개 중 하나이다.
{A, C, F, J, M, N, R, T}각각 어피치, 콘, 프로도, 제이지, 무지, 네오, 라이언, 튜브를 의미한다. 첫 번째 글자는 조건을 제시한 프렌즈, 세 번째 글자는 상대방이다. 첫 번째 글자와 세 번째 글자는 항상 다르다. - 두 번째 글자는 항상
~이다. - 네 번째 글자는 다음 3개 중 하나이다.
{=, <, >}각각 같음, 미만, 초과를 의미한다. - 다섯 번째 글자는
0이상6이하의 정수의 문자형이며, 조건에 제시되는 간격을 의미한다. 이때 간격은 두 프렌즈 사이에 있는 다른 프렌즈의 수이다.
- 첫 번째 글자와 세 번째 글자는 다음 8개 중 하나이다.
출력 형식
모든 조건을 만족하는 경우의 수를 리턴한다.
예제 입출력
| n | data | answer |
|---|---|---|
| 2 | ["N~F=0", "R~T>2"] | 3648 |
| 2 | ["M~C<2", "C~M>1"] | 0 |
예제에 대한 설명
첫 번째 예제는 문제에 설명된 바와 같이, 네오는 프로도와의 간격이 0이기를 원하고 라이언은 튜브와의 간격이 2보다 크기를 원하는 상황이다.
두 번째 예제는 무지가 콘과의 간격이 2보다 작기를 원하고, 반대로 콘은 무지와의 간격이 1보다 크기를 원하는 상황이다. 이는 동시에 만족할 수 없는 조건이므로 경우의 수는 0이다.
✏️풀이
코드
class Solution {
// 카카오프렌즈를 저장할 배열
char[] friends;
int answer;
// 방문여부를 저장할 배열
boolean[] visited;
// 조건을 만족하는지 확인하는 메소드
public boolean check(String line, String[] data) {
// 조건들의 개수만큼 반복
for(String cond : data) {
// 조건과 비교할 차이를 저장
int diff = Math.abs(line.indexOf(cond.charAt(0)) - line.indexOf(cond.charAt(2))) - 1;
// 조건에서 원하는 범위를 저장
char sign = cond.charAt(3);
// 조건에서 원하는 차이를 저장
int value = cond.charAt(4) - '0';
// 각각의 조건을 확인하여 조건과 일치하지 않는다면 false를 반환
if(sign == '=') {
if(diff != value) {
return false;
}
} else if(sign == '>') {
if(diff <= value) {
return false;
}
} else if(sign == '<') {
if(diff >= value) {
return false;
}
}
}
// 모든 조건과 일치한다면 true를 반환
return true;
}
// dfs 탐색 메소드
public void dfs(String line, String[] data, int depth) {
// 모든 프렌즈가 줄을 다 섰을 경우
if(depth == 8) {
// 해당 경우의 수가 조건에 만족하는지 확인
if(check(line, data)) {
answer++;
}
return;
}
// 프렌즈의 수만큼 반복
for(int i = 0; i < 8; i++) {
// 방문한 적 없다면
if(!visited[i]) {
// 방문여부를 true로 바꾸고
visited[i] = true;
// 다시 탐색을 진행
dfs(line + friends[i], data, depth + 1);
// 탐색이 종료된 뒤 false로 바꿔줌
visited[i] = false;
}
}
}
public int solution(int n, String[] data) {
answer = 0;
friends = new char[] {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
visited = new boolean[8];
dfs("", data, 0);
return answer;
}
}설명
dfs 탐색을 사용하여 진행하였다.
check 메소드의 매개변수들이 가지는 뜻은 다음과 같다.
- String line
- 모든 프렌즈들이 줄을 선 경우
- String[] data
- 프렌즈들이 원하는 조건들을 저장한 배열
조건의 개수만큼 반복을 진행한다.
조건의 형태는 N~F=0 이다. 따라서 charAt(0)과 charAt(2)는 조건을 원하는 사람과 대상자를 뜻한다. charAt(3)은 해당 조건을 뜻하며, charAt(4)는 그 길이를 뜻한다.
예를 들어, N~F=0일 경우 네오와 프로도와의 간격이 0이길 원한다는 뜻이다. 따라서 현재 line에서 네오와 프로도의 위치를 구하고 해당 간격이 0인지 확인을 해야하는 것이다.
각각의 값들을 저장해준 뒤에 if문을 활용하여 조건들을 확인하고 조건에 일치하지 않는다면 false를 모든 조건에 일치한다면 true를 반환해준다.
dfs 탐색 메소드의 매개변수들이 가지는 뜻은 다음과 같다.
- String line
- 모든 프렌즈들이 줄을 선 경우
- String[] data
- 프렌즈들이 원하는 조건들을 저장한 배열
- int depth
- 탐색의 깊이
프렌제의 수만큼 반복을 진행하여 줄을 아직 서지 않았다면 line에 값을 추가해준 뒤에 다시 dfs 메소드를 호출하여 탐색을 진행한다. 이때 탐색의 깊이가 8인 경우, 즉 모든 프렌즈가 줄을 다 섰을 경우에는 줄을 선 방법이 data에 있는 조건들에 만족하는지 check 메소드를 호출하여 확인하고 만족한다면 answer의 값을 증가시킨다.
solution 메소드에서는 friends, visited, answer를 초기화해준 뒤 dfs 탐색을 진행한다. 이후 모든 탐색이 끝난 뒤에 answer에 저장된 값을 반환해주면 문제를 해결할 수 있다!
💡느낀 점
이전에도 많이 사용했던 dfs 탐색의 방식이라 생각하고 코드를 짜는 부분에서 어렵지 않게 느껴졌다. 그러나 당황을 한 부분이 있다면 코드 채점을 했을 때 테스트가 한가지 밖에 없었다는 것.. 문제를 풀면서 테스트가 한가지 밖에 없는 경우는 처음이라 풀이보다 채점에 더 신기함을 느꼈던 문제였다ㅎㅎ
링크
java로 카카오프렌즈 주제로 코딩하신거 인상 깊었습니다.