문제 이해 단계
https://school.programmers.co.kr/learn/courses/30/lessons/92343?
이진트리가 있는데, 각 노드에는 양(0) 또는 늑대(1)가 있다.
무조건 루트노드에서 출발하여 양을 획득해야 한다.
루트 노드는 항상 양이다.
획득하는 과정에서 양의 수가 항상 늑대 수보다 많음을 유지해야 한다.
최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아올 때
모을 수 있는 최대 양의 수를 구하는 문제
문제 접근 단계
제한 사항 파악
제한 사항부터 보면 노드(info)는 최대 17개까지이다.
이에 따라, 항상 이진트리를 유지하기 때문에
간선(edges) 또한 100개가 넘어가지 않는다
즉, 완전 탐색이 가능할 만큼 탐색할 범위가 작음을 알 수가 있다.
움직이는 경로
해당 문제 설명에서
"최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아온다"라고 적혀있다.
우리는 여기서 한 가지를 알 수 있는데,
이미 방문했던 노드를 다시 방문하는 경우가 자주 생긴다는 것이다.
왜냐하면 루트노드에서 출발해서 양을 획득해서 돌아오려면,
이미 방문했던 노드를 다시 지나가는 수밖에 없다.
이동할 수 있는 경우의 수
그다음으로 따져봐야 할 것은
어떤 경우에 다음 노드로 갈 수 있냐는 것이다.
총 2가지 경우가 있을 것이다.
1. 다음 노드가 '양'
2. 다음 노드가 '늑대'
1번의 경우,
(현재 양의 수 > 현재 늑대의 수)가 항상 유지되기 때문에,
다음 노드가 양이라면 바로 움직여도 된다.
2번의 경우,
(현재 양의 수 > 현재 늑대의 수 + 1)를 만족해야지만 이동할 수 있다.
왜냐하면 다음 노드에서 얻을 늑대까지 고려해야 하기 때문이다.
사실 이동에는 한 가지 경우의 수가 더 존재한다.
해당 노드에서 양이나 늑대를 획득하고, 한번 더 그 노드를 방문했을 때이다.
그림을 보면 좀 더 이해하기 편할 것이다.
이런 식으로 이미 방문했던 곳은 양이든, 늑대든 없기 때문에 빈 노드가 된다.
이런 경우 빈 노드인 경우에도 물론 그냥 지나갈 수 있다.
중복 방문을 피하면서 양 획득하기
이 문제에서 가장 까다로운 부분이다.
결국 이진트리를 탐색하기 위해서는 그래프 탐색을 사용해야 하는데,
위에서 말했듯이 이미 갔던 곳을 다시 지나갈 수 있다.
그렇다고 방문처리가 없으면 영원히 탐색을 할 것이다. 어떻게 이를 처리해야 할까?
방문에 이 문제의 키워드 3가지를 사용하면 된다.
키워드 3가지는 (노드, 양, 늑대)이다.
그래서 이런 식으로 나타낸다.
visit [A][B][C] = true/false
A번 노드에 현재 B개의 양과 C개의 늑대를 가진 채로 방문 한 적 있다/없다.
이를 이용하여 방문 배열로 하여 DFS를 한다.
그리고 3개의 이동가능한 경우에 따라 처리해 준다.
위에서 이동 가능한 경우 3가지를 나눴다.
이에 따라 방문처리를 다르게 해 준다.
1. 다음 노드 A가 '양'
visit [A][B+1][C]를 방문했는지 확인
방문하지 않았다면 노드 A로 이동
2. 다음 노드 A가 '늑대'
visit [A][B][C+1]를 방문했는지 확인
방문하지 않았고 (양 > 늑대 + 1) 일 경우에만 노드 A로 이동
3. 다음 노드 A가 빈 노드
visit [A][B][C]를 방문했는지 확인
방문하지 않았다면 노드 A로 이동
2번의 경우를 주의한다.
(양 > 늑대+1)을 만족하지 않을 경우 이동하지 않는다.
이제 이를 토대로 문제 구현 단계에서
C++과 C#으로 코드로 구현해 보자.
문제 구현 단계
C++로 구현한 코드
↓
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool visited[18][18][18] = {false,};
vector<int> node[18]; // 연결 상태
vector<int> kind; // 해당 노드의 상태
int ans = 0; // 최대 양의 수
void dfs(int x, int sheep, int wolf){
ans = max(ans,sheep); // 최대 양의 수를 답으로 선택
// 연결되어 있는 부모,자식 노드 모두 확인
for(int i = 0; i < node[x].size(); i++){
int nx = node[x][i];
// 다음 노드가 '양' && 방문하지 않은 경우
if(kind[nx] == 0 && !visited[nx][sheep+1][wolf]){
visited[nx][sheep+1][wolf] = true;
kind[nx] = -1; // 빈 노드로 바꿔줌
dfs(nx,sheep+1,wolf); // 재귀 호출
// 사용 후 다른 DFS가 호출할 수 있도록 원상복구
kind[nx] = 0;
visited[nx][sheep+1][wolf] = false;
}
// 다음 노드가 '늑대'
else if(kind[nx] == 1){
// 양 > 늑대+1 && 방문하지 않은 경우에만 다음 노드로 이동
if(sheep > wolf+1 && !visited[nx][sheep][wolf+1]){
visited[nx][sheep][wolf+1] = true;
kind[nx] = -1;
dfs(nx,sheep,wolf+1);
kind[nx] = 1;
visited[nx][sheep][wolf+1] = false;
}
}
// 다음 노드가 빈 노드인 경우
else{
if(!visited[nx][sheep][wolf]){
visited[nx][sheep][wolf] = true;
dfs(nx,sheep,wolf);
visited[nx][sheep][wolf] = false;
}
}
}
}
int solution(vector<int> info, vector<vector<int>> edges) {
for(int i = 0; i < edges.size(); i++){
node[edges[i][0]].push_back(edges[i][1]);
node[edges[i][1]].push_back(edges[i][0]);
}
for(int i = 0; i < info.size(); i++) kind.push_back(info[i]);
kind[0] = -1; // 루트 노드 빈 노드로
visited[0][1][0] = true; // 루트 노드 방문 처리
dfs(0,1,0); // 루트 노드에서 양 얻은 채로 시작
return ans;
}↑
C#으로 구현한 코드
↓
using System;
using System.Collections.Generic;
public class Solution {
static List<int>[] node = new List<int>[20]; // 연결된 노드
static List<int> kind = new List<int>(); // 해당 노드의 상태
static bool[,,] visited = new bool[20,20,20]; // 3차원으로 선언한 방문처리
static int ans = 0; // 획득 가능한 양의 최대 개수
static void Dfs(int x, int sheep, int wolf){
ans = Math.Max(ans,sheep); // 가질 수 있는 최대를 반환
// 해당 노드와 연결된 부모, 자식 노드 전부를 탐색
for(int i = 0; i < node[x].Count; i++)
{
int nx = node[x][i];
// 다음 노드가 '양' && 방문하지 않은 경우
if(kind[nx] == 0 && !visited[nx,sheep+1,wolf]) {
visited[nx,sheep+1,wolf] = true; // 방문처리
kind[nx] = -1; // 해당 노드를 빈 노드로 만듬
Dfs(nx,sheep+1,wolf); // 해당 노드를 메인으로 DFS 호출
// 다른 DFS가 사용 가능하도록 원상복구
kind[nx] = 0;
visited[nx,sheep+1,wolf] = false;
}
// 다음 노드가 '늑대'
else if(kind[nx] == 1){
// 양 > 늑대+1 && 방문하지 않은 경우에만 다음 노드로 이동
if(sheep > wolf+1 && !visited[nx,sheep,wolf+1])
{
visited[nx,sheep,wolf+1] = true;
kind[nx] = -1;
Dfs(nx,sheep,wolf+1);
kind[nx] = 1;
visited[nx,sheep,wolf+1] = false;
}
}
// 다음 노드가 빈 노드인 경우
else{
if(!visited[nx,sheep,wolf]){
visited[nx,sheep,wolf] = true;
Dfs(nx,sheep,wolf);
visited[nx,sheep,wolf] = false;
}
}
}
}
public int solution(int[] info, int[,] edges) {
for(int i = 0; i < 18; i++) node[i] = new List<int>();
for(int i = 0; i < info.Length; i++) kind.Add(info[i]);
for(int i = 0; i < edges.GetLength(0); i++){
node[edges[i,0]].Add(edges[i,1]);
node[edges[i,1]].Add(edges[i,0]);
}
kind[0] = -1; // 루트 노드 빈 노드로
visited[0,1,0] = true; // 루트 노드 방문 처리
Dfs(0,1,0); // 루트 노드에서 양 얻은 채로 시작
int answer = ans;
return answer;
}
}↑
C++이나 C#이나 코드나 기술적으로 크게 다른 부분은 없기 때문에 같이 설명하겠다.
기본적인 토대는 일반적인 DFS와 같다.
방문처리만 3차원으로 했을 뿐 크게 다를 것은 없다.
가장 처음 edges를 양방향으로 연결해 준 것은,
자식 노드로 갔다가 다시 돌아와야 하기 때문에 양방향 이동이 필요하기 때문이다.
그리고 양이나 늑대를 획득한 노드를 -1로 처리해서 빈 노드로 만들어준다.
그것 외에는 일반적인 DFS와 같고,
코드에 있는 주석으로 충분히 이해가 가능하기 때문에 생략하겠다.
시행착오
처음에는 백준에 있는 '열쇠'라는 문제랑 비슷한 문제인 줄 알았는데, 전혀 아니었다.
계속 그렇게 풀다가, 틀리고 한 3~4시간이 지나고서야 알았다.
방문배열을 3차원으로 써야 된다는 생각을 왜 못했지..
아마 인터넷을 참고하지 못했으면 풀지 못했을 것 같다.
프로그래머스 문제 힘들다.. ㅠㅠ
생활비..