오지 탐험가인프로도는 탐험 도중 n개의 방으로 이루어진 지하 동굴을 탐험하게 되었습니다. 모든 방에는 0부터 n - 1 까지 번호가 붙어있고, 이 동굴에 들어갈 수 있는 유일한 입구는 0번 방과 연결되어 있습니다. 각 방들은 양방향으로 통행이 가능한 통로로 서로 연결되어 있는데, 서로 다른 두 방을 직접 연결하는 통로는 오직 하나입니다. 임의의 서로 다른 두 방 사이의 최단경로는 딱 한 가지만 있으며, 또한 임의의 두 방 사이에 이동이 불가능한 경우는 없습니다.
탐험에 앞서 이 지하 동굴의 지도를 손에 넣은 프로도는 다음과 같이 탐험 계획을 세웠습니다.
모든 방을 적어도 한 번은 방문해야 합니다.
특정 방은 방문하기 전에 반드시 먼저 방문할 방이 정해져 있습니다. 2-1. 이는 A번 방은 방문하기 전에 반드시 B번 방을 먼저 방문해야 한다는 의미입니다. 2-2. 어떤 방을 방문하기 위해 반드시 먼저 방문해야 하는 방은 없거나 또는 1개 입니다. 2-3. 서로 다른 두 개 이상의 방에 대해 먼저 방문해야 하는 방이 같은 경우는 없습니다. 2-4. 어떤 방이 먼저 방문해야 하는 방이면서 동시에 나중에 방문해야 되는 방인 경우는 없습니다.
위 계획 중 2-2, 2-3, 2-4는 순서를 지켜 방문해야 하는 두 방의 쌍이A → B(A를 먼저 방문하고 B를 방문함) 형태로 유일함을 의미합니다. 즉, 프로도는 아래와 같은 형태로 방문순서가 잡히지 않도록 방문 계획을 세웠습니다.
A → B, A → C(방문순서 배열 order = [...,[A,B],...,[A,C],...]) 형태로 A를 방문 후에 방문해야 할 방이 B와 C로 두 개 또는 그 이상인 경우
X → A, Z → A(방문순서 배열 order = [...,[X,A],...,[Z,A],...]) 형태로 A를 방문하기 전에 방문해야 할 방이 X와 Z로 두 개 또는 그 이상 인 경우
A → B → C(방문순서 배열 order = [...,[A,B],...,[B,C],...) 형태로 B처럼 A 방문 후이면서 동시에 C 방문 전인 경우
그리고 먼저 방문해야 할 방과 나중에 방문할 방을 반드시 연속해서 방문해야 할 필요는 없어 A방을 방문한 후 다른 방을 방문한 후 B방을 방문해도 좋습니다.
방 개수 n, 동굴의 각 통로들이 연결하는 두 방의 번호가 담긴 2차원 배열 path, 프로도가 정한 방문 순서가 담긴 2차원 배열 order가 매개변수로 주어질 때, 프로도가 규칙에 맞게 모든 방을 탐험할 수 있을 지 return 하도록 solution 함수를 완성해주세요.
[제한사항]
n은 2 이상 200,000 이하입니다.
path 배열의 세로(행) 길이는 n - 1 입니다.
path 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다.
두 방 A, B사이를 연결하는 통로를 나타냅니다.
통로가 연결하는 두 방 번호가 순서없이 들어있음에 주의하세요.
order 배열의 세로(행) 길이는 1 이상 (n / 2) 이하입니다.
order 배열의 원소는 [방 번호 A, 방 번호 B] 형태입니다.
A번 방을 먼저 방문한 후 B번 방을 방문해야 함을 나타냅니다.
입출력 예
npathorderresult
9
[[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]]
[[8,5],[6,7],[4,1]]
true
9
[[8,1],[0,1],[1,2],[0,7],[4,7],[0,3],[7,5],[3,6]]
[[4,1],[5,2]]
true
9
[[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]]
[[4,1],[8,7],[6,5]]
false
입출력 예에 대한 설명
접근 방법
결론부터 이야기하자면 DFS를 사용하여 구현하였습니다. 효율성 10번 테스트케이스에서 런타임에러가 발생하는데 Java 환경에서는 BFS를 사용해야만 통과할 수 있을 거 같습니다. C++의 경우 DFS를 사용해도 무난히 통과할 수 있습니다.
이런 유형의 문제는 처음이여서 다른 사람들의 풀이를 참조하였습니다.
*order에서 [A -> B]가 존재한다고 할 때 A를 B의 사전노드, B를 A의 사후노드라고 표현하겠습니다.
1. 현재 방문하고자 하는 노드가 사전 노드를 가지고 있는지 확인합니다.
2. 사전 노드가 방문이 된 상태라면 DFS를 계속 진행합니다.
3. 사전 노드가 방문이 되지 않은 상태라면 현재 노드와 사전 노드를 reserve에 기록하고 DFS진행을 멈춥니다.
4. 이후 현재노드가 reserve에 기록되어 있다면, 즉시 사후노드부터 DFS를 진행시킵니다.
자세한 내용은 소스코드에 주석처리 하겠습니다.
소스 코드
import java.util.*;
class Solution {
ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>>(); //인접 리스트
HashMap<Integer, Integer> before = new HashMap<Integer, Integer>(); //(사후노드, 사전노드)
HashMap<Integer, Integer> reserve = new HashMap<Integer, Integer>(); //(사전노드, 사후노드)
boolean visited[] = new boolean[200000];
int cnt = 0; //노드의 방문 횟수
public void init(int n, int[][] path, int[][] order){
for(int i=0;i<n;i++)
tree.add(new ArrayList<Integer>());
for(int i=0;i<order.length;i++)
before.put(order[i][1], order[i][0]);
for(int i=0;i<path.length;i++){
tree.get(path[i][0]).add(path[i][1]);
tree.get(path[i][1]).add(path[i][0]);
}
}
public void DFS(int now){
//사전노드를 가지고 있는지 검사
if(before.get(now) != null){
//사전 노드가 방문된 상태가 아니라면 기록 후 진행을 멈춤
if(!visited[before.get(now)]){
reserve.put(before.get(now), now);
return;
}
}
visited[now] = true;
++cnt; //노드의 방문 횟수
//만약 사후노드가 방문되었다면 사전 노드부터 탐색
if(reserve.get(now) != null)
DFS(reserve.get(now));
//인접한 노드들로 DFS진행
for(int i=0;i<tree.get(now).size();i++){
int next = tree.get(now).get(i);
if(!visited[next])
DFS(next);
}
return;
}
public boolean solution(int n, int[][] path, int[][] order) {
boolean answer = true;
init(n, path, order); DFS(0);
//모든 노드를 방문했다면 true, 아니면 false
return answer = (cnt == n) ? true : false;
}
}
각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다.
임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한쪽은 1 감소시킵니다.
하지만, 모든 트리가 위의 행동을 통하여 모든 점들의 가중치를 0으로 만들 수 있는 것은 아닙니다. 당신은 주어진 트리에 대해서 해당 사항이 가능한지 판별하고, 만약 가능하다면 최소한의 행동을 통하여 모든 점들의 가중치를 0으로 만들고자 합니다.
트리의 각 점의 가중치를 의미하는 1차원 정수 배열a와 트리의 간선 정보를 의미하는edges가 매개변수로 주어집니다. 주어진 행동을 통해 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 최소 몇 번만에 가능한지를 찾아 return 하도록 solution 함수를 완성해주세요. (만약 처음부터 트리의 모든 정점의 가중치가 0이라면, 0을 return 해야 합니다.)
제한사항
a의 길이는 2 이상 300,000 이하입니다.
a의 모든 수는 각각 -1,000,000 이상 1,000,000 이하입니다.
a[i]는 i번 정점의 가중치를 의미합니다.
edges의 행의 개수는 (a의 길이 - 1)입니다.
edges의 각 행은[u, v]2개의 정수로 이루어져 있으며, 이는 u번 정점과 v번 정점이 간선으로 연결되어 있음을 의미합니다.
edges가 나타내는 그래프는 항상 트리로 주어집니다.
입출력 예
aedgesresult
[-5,0,2,1,2]
[[0,1],[3,4],[2,3],[0,3]]
9
[0,1,0]
[[0,1],[1,2]]
-1
입출력 예 설명
입출력 예 #1
다음 그림은 주어진 트리의 모든 정점의 가중치를 0으로 만드는 과정을 나타낸 것입니다.
2번 정점과 3번 정점을 선택하여 2번 정점은 1 감소시키고, 3번 정점은 1 증가시킵니다. (2번 반복)
3번 정점과 4번 정점을 선택하여 4번 정점은 1 감소시키고, 3번 정점은 1 증가시킵니다. (2번 반복)
0번 정점과 3번 정점을 선택하여 3번 정점은 1 감소시키고, 0번 정점은 1 증가시킵니다. (5번 반복)
모든 정점의 가중치를 0으로 만드는 데 필요한 최소 행동 횟수는 9번이므로, 9를 return 해야 합니다.
입출력 예 #2
주어진 트리는 모든 정점의 가중치를 0으로 만드는 것이 불가능하므로, -1을 return 해야 합니다.
접근 방법
1. 가장 먼저 확인해야할 부분은 모두 0으로 만들 수 있는지 아닌지 입니다.
모든 노드의 가중치의 합이 0이라면 모두 0으로 만드는 것이 가능하고, 반대의 경우는 모든 가중치를 0으로 만드는 것이 불가능합니다.
2. 어떻게 해야 최소의 횟수로 모든 가중치를 0으로 만들 수 있을까?
가장 최소의 횟수로 모든 가중치를 0으로 만드려면 반복되는 연산(가중치 교환)과정이 있어서는 안됩니다. 즉 일방향으로 연산을 적용한다면 노드의 어떤 부분부터 시작하더라도 모두 같은 최솟값을 구할 수 있습니다.
노드의 연결 정보는 무조건 트리의 형태로 주어진다는 것을 알 수 있습니다. 즉 어떤 임의의 노드를 루트로 잡고 DFS를 사용하여 자식의 방향으로 향하게 설계 후, 리프(말단)노드로부터 부모 노드의 방향으로 연산을 적용하여 해결할 수 있습니다.
소스 코드
import java.util.*;
class Solution {
ArrayList<ArrayList<Integer>> info;
boolean[] visited;
long[] a;
long cnt = 0;
void solve(int now){
//부모노드로 올라가지 못하게 방문노드 check
visited[now] = true;
for(int i=0;i<info.get(now).size();i++){
int next = info.get(now).get(i);
if(visited[next] == false){
solve(next);
a[now] += a[next];
}
}
//cnt는 연산이 일어나는 횟수
cnt += Math.abs(a[now]);
}
void makeInfo(int[][] edges){
info = new ArrayList<ArrayList<Integer>>();
for(int i=0;i<this.a.length;i++)
info.add(new ArrayList<Integer>());
for(int i=0;i<edges.length;i++){
info.get(edges[i][0]).add(edges[i][1]);
info.get(edges[i][1]).add(edges[i][0]);
}
}
public long solution(int[] a, int[][] edges) {
long sum = 0;
this.a = new long[a.length];
this.visited = new boolean[a.length];
for(int i=0;i<a.length;i++){
this.a[i] = a[i];
sum += this.a[i];
}
//합이 0이 아니라면 가중치를 0으로 만들 수 없음
if(sum != 0)
return -1;
//인접리스트로 표현
makeInfo(edges);
solve(0);
return cnt;
}
}
프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.
그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.
후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.
관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.
제이지를 위해, 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.
위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 "학번"을 가지고 있다. 따라서 "학번"은 릴레이션의 후보 키가 될 수 있다. 그다음 "이름"에 대해서는 같은 이름("apeach")을 사용하는 학생이 있기 때문에, "이름"은 후보 키가 될 수 없다. 그러나, 만약 ["이름", "전공"]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다. 물론 ["이름", "전공", "학년"]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다. 따라서, 위의 학생 인적사항의 후보키는 "학번", ["이름", "전공"] 두 개가 된다.
릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.
제한사항
relation은 2차원 문자열 배열이다.
relation의 컬럼(column)의 길이는1이상8이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
relation의 로우(row)의 길이는1이상20이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
relation의 모든 문자열의 길이는1이상8이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
게임 개발자인베로니는 개발 연습을 위해 다음과 같은 간단한 카드 짝맞추기 보드 게임을 개발해 보려고 합니다. 게임이 시작되면 화면에는 카드 16장이 뒷면을 위로하여4 x 4크기의 격자 형태로 표시되어 있습니다. 각 카드의 앞면에는 카카오프렌즈 캐릭터 그림이 그려져 있으며, 8가지의 캐릭터 그림이 그려진 카드가 각기 2장씩 화면에 무작위로 배치되어 있습니다. 유저가 카드를 2장 선택하여 앞면으로 뒤집었을 때 같은 그림이 그려진 카드면 해당 카드는 게임 화면에서 사라지며, 같은 그림이 아니라면 원래 상태로 뒷면이 보이도록 뒤집힙니다. 이와 같은 방법으로 모든 카드를 화면에서 사라지게 하면 게임이 종료됩니다.
게임에서 카드를 선택하는 방법은 다음과 같습니다.
카드는커서를 이용해서 선택할 수 있습니다.
커서는 4 x 4 화면에서 유저가 선택한 현재 위치를 표시하는굵고 빨간 테두리 상자를 의미합니다.
커서는 [Ctrl] 키와 방향키에 의해 이동되며 키 조작법은 다음과 같습니다.
방향키 ←, ↑, ↓, → 중 하나를 누르면, 커서가 누른 키 방향으로 1칸 이동합니다.
[Ctrl] 키를 누른 상태에서 방향키 ←, ↑, ↓, → 중 하나를 누르면, 누른 키 방향에 있는 가장 가까운 카드로 한번에 이동합니다.
만약, 해당 방향에 카드가 하나도 없다면 그 방향의 가장 마지막 칸으로 이동합니다.
만약, 누른 키 방향으로 이동 가능한 카드 또는 빈 공간이 없어 이동할 수 없다면 커서는 움직이지 않습니다.
커서가 위치한 카드를 뒤집기 위해서는 [Enter] 키를 입력합니다.
[Enter] 키를 입력해서 카드를 뒤집었을 때
앞면이 보이는 카드가 1장 뿐이라면 그림을 맞출 수 없으므로 두번째 카드를 뒤집을 때 까지 앞면을 유지합니다.
앞면이 보이는 카드가 2장이 된 경우, 두개의 카드에 그려진 그림이 같으면 해당 카드들이 화면에서 사라지며, 그림이 다르다면 두 카드 모두 뒷면이 보이도록 다시 뒤집힙니다.
베로니는 게임 진행 중 카드의 짝을 맞춰 몇 장 제거된 상태에서 카드 앞면의 그림을 알고 있다면, 남은 카드를 모두 제거하는데 필요한 키 조작 횟수의 최솟값을 구해 보려고 합니다. 키 조작 횟수는 방향키와 [Enter] 키를 누르는 동작을 각각 조작 횟수1로 계산하며, [Ctrl] 키와 방향키를 함께 누르는 동작 또한 조작 횟수1로 계산합니다.
다음은 카드가 몇 장 제거된 상태의 게임 화면에서 커서를 이동하는 예시입니다. 아래 그림에서 빈 칸은 이미 카드가 제거되어 없어진 칸을 의미하며, 그림이 그려진 칸은 카드 앞 면에 그려진 그림을 나타냅니다.
예시에서 커서는 두번째 행, 첫번째 열 위치에서 시작하였습니다.
[Enter] 입력, ↓ 이동, [Ctrl]+→ 이동, [Enter] 입력 = 키 조작 4회
[Ctrl]+↑ 이동, [Enter] 입력, [Ctrl]+← 이동, [Ctrl]+↓ 이동, [Enter] 입력 = 키 조작 5회
[Ctrl]+→ 이동, [Enter] 입력, [Ctrl]+↑ 이동, [Ctrl]+← 이동, [Enter] 입력 = 키 조작 5회
위와 같은 방법으로 커서를 이동하여 카드를 선택하고 그림을 맞추어 카드를 모두 제거하기 위해서는 총 14번(방향 이동 8번, [Enter] 키 입력 6번)의 키 조작 횟수가 필요합니다.
[문제]
현재 카드가 놓인 상태를 나타내는 2차원 배열 board와 커서의 처음 위치 r, c가 매개변수로 주어질 때, 모든 카드를 제거하기 위한 키 조작 횟수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.
[제한사항]
board는 4 x 4 크기의 2차원 배열입니다.
board 배열의 각 원소는 0 이상 6 이하인 자연수입니다.
0은 카드가 제거된 빈 칸을 나타냅니다.
1 부터 6까지의 자연수는 2개씩 들어있으며 같은 숫자는 같은 그림의 카드를 의미합니다.
뒤집을 카드가 없는 경우(board의 모든 원소가 0인 경우)는 입력으로 주어지지 않습니다.
r은 커서의 최초 세로(행) 위치를 의미합니다.
c는 커서의 최초 가로(열) 위치를 의미합니다.
r과 c는 0 이상 3 이하인 정수입니다.
게임 화면의 좌측 상단이 (0, 0), 우측 하단이 (3, 3) 입니다.
[입출력 예]
boardrcresult
[[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]]
1
0
14
[[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]]
0
1
16
접근 방법
삼성 유형과 비슷한 문제였는데 상당히 복잡하게 느껴졌습니다.
일단 문제의 큰 틀을 잡아보면 4가지 과정으로 나눌 수 있습니다.
1. 어떤 짝 먼저 맞춰갈지에 대한 순서 정하기
2. 순서를 정했다면 한 쌍에서 어떤 카드부터 선택 할지 정하기
3. 2번 과정까지 완료 됬다면 각각 지점사이에 이동 횟수를 알아내어 전체 경로의 이동횟수를 구하기
4. 3번 과정을 반복하며 최소값 갱신
1. 어떤 짝 먼저 맞춰갈지에 대한 순서 정하기
만약 짝이 1,2,3이 있다면 1->2->3 순서로 해결할지 1->3->2의 순서로 해결할지
void moveAll(info &shark) {
vector<pair<int, int>> fishInfo(17, {-1,-1}); //n번 물고기와 좌표를 매핑
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (!(i == shark.x && j == shark.y))
if (map[i][j].num != 0)
fishInfo[map[i][j].num] = { i,j };
for (int i = 1; i < 17; i++)
if (fishInfo[i].first != -1)
move(fishInfo, shark, i);
}
2. fishInfo를 1번 부터 탐색하며 한 마리 씩 이동시킨다. 이 때 물고기가 이동하며 swap되는 정보가 fishInfo에 실시간으로 갱신되야 하므로 move()함수에 fishInfo를 참조 연산자로 넘겨주었다.
void move(vector<pair<int, int>> &fishInfo, info shark, int num) {
int x = fishInfo[num].first;
int y = fishInfo[num].second;
int dir = map[x][y].dir;
for (int i = 0; i < 8; i++) {
int next_dir = (dir + i) % 8;
int next_x = x + direction[next_dir].first;
int next_y = y + direction[next_dir].second;
if (inRange(next_x, next_y) && !(next_x == shark.x && next_y == shark.y)) { //이동가능 하다면 swap
fish tmp = map[next_x][next_y];
map[next_x][next_y] = { num, next_dir };
map[x][y] = tmp;
fishInfo[num] = { next_x, next_y };
fishInfo[tmp.num] = { x,y };
break;
}
}
}
자세한 내용은 하단의 소스코드에 주석을 남겨두었음
소스 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef struct fish {
int num, dir;
};
typedef struct info {
int x, y, dir, cost;
};
pair<int, int> direction[8] = { {-1, 0}, {-1,-1}, {0,-1}, {1,-1}, {1,0}, {1,1}, {0,1}, {-1,1} };
fish map[4][4];
info shark;
int result = 0;
bool inRange(int x, int y) {
return (0 <= x && x < 4 && 0 <= y && y < 4);
}
vector<vector<fish>> copy() {
vector<vector<fish>> repos(4, vector<fish>(4));
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
repos[i][j] = map[i][j];
return repos;
}
void restore(vector<vector<fish>> repos) {
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
map[i][j] = repos[i][j];
}
void move(vector<pair<int, int>> &fishInfo, info shark, int num) {
//한 마리의 물고기에 대한 처리
//실시간으로 fishInfo를 업데이트 해야 하므로 참조 연산자 사용
int x = fishInfo[num].first;
int y = fishInfo[num].second;
int dir = map[x][y].dir;
for (int i = 0; i < 8; i++) { //반 시계 방향으로 방향 전환
int next_dir = (dir + i) % 8;
int next_x = x + direction[next_dir].first;
int next_y = y + direction[next_dir].second;
if (inRange(next_x, next_y) && !(next_x == shark.x && next_y == shark.y)) { //이동가능 하다면 swap
fish tmp = map[next_x][next_y];
map[next_x][next_y] = { num, next_dir };
map[x][y] = tmp;
fishInfo[num] = { next_x, next_y };
fishInfo[tmp.num] = { x,y };
break; // 물고기 이동 후 종료
}
}
}
void moveAll(info &shark) { // 전체 물고기에 대해
vector<pair<int, int>> fishInfo(17, {-1,-1}); //n번 물고기와 좌표를 매핑
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (!(i == shark.x && j == shark.y))
if (map[i][j].num != 0)
fishInfo[map[i][j].num] = { i,j };
for (int i = 1; i < 17; i++)
if (fishInfo[i].first != -1)
move(fishInfo, shark, i); //1번 부터 1마리 씩 이동
}
bool goHome(info &shark) {
int x = shark.x;
int y = shark.y;
while (inRange(x, y)) { //범위 안에서 물고기가 있는지 확인
if (map[x][y].num != 0)
return false;
x += direction[shark.dir].first;
y += direction[shark.dir].second;
}
return true;
}
void solve(info shark) {
//repos를 전역변수로 사용한다면 다른 dfs에서 repos의 상태를 변화시킬 수 있으므로 불가능
vector<vector<fish>> repos = copy();
moveAll(shark); // 물고기 전부 이동
if (goHome(shark)) { //먹을 먹이가 없다면
result = max(shark.cost, result); //결과 갱신
restore(repos); //map복원
return;
}
else {
int x = shark.x + direction[shark.dir].first;
int y = shark.y + direction[shark.dir].second;
while (inRange(x, y)) {
if (map[x][y].num != 0) {
fish tmp = map[x][y];
map[x][y] = { 0, 0 }; //해당 좌표의 물고기를 먹음
solve({ x, y, tmp.dir, shark.cost + tmp.num }); //next
map[x][y] = tmp; //back
}
x += direction[shark.dir].first;
y += direction[shark.dir].second;
}
restore(repos); //map 복원
}
}
int main() {
ios_base::sync_with_stdio(false);
cout.tie(0);
cin.tie(0);
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
int num, dir;
cin >> num >> dir;
map[i][j] = { num, dir - 1 };
}
}
shark = { 0,0, map[0][0].dir, map[0][0].num };
map[0][0] = { 0,0 };
result = shark.cost;
solve(shark);
cout << result << "\n";
}
1. DFS를 통해 순열을 구한다. 이 때 cnt=3(4번 타자)는 고정이므로 pass하고, 순열이 완성 되었을 때 게임의 점수를 구하는 play_game()함수를 실행한다.
int solve(int cnt) {
int maximum = 0;
if (cnt == 3) //4번 타자는 pass
cnt++;
if (cnt == 9) {
return play_game();
}
for (int i = 0; i < 9; i++) {
if (!visited[i]) { //방문 여부
visited[i] = true;
seq[cnt] = i;
maximum = max(maximum, solve(cnt + 1));
visited[i] = false;
}
}
return maximum;
}
2. while문을 통해 한 이닝이 끝났을 때 점수(sum)를 더해주며, 다음 이닝의 선두주자(now)를 갱신한다.
int play_game() { //순서가 결정 되었을 때
int inning = -1;
int now = 0;
int sum = 0;
while (++inning < N) {
pair<int, int> info = oneInning(inning, now);
sum += info.first;
now = info.second;
}
return sum;
}
3. base는 홈 부터 1,2,3루를 의미하며, 아웃(info[inning][hitter] == 0)인 경우 변수out을 증가시켜 반복한다. out이 아니라면 각각의 타자가 친 정보를 통해 move()함수를 실행하여 base를 갱신하며 점수를 구한다.
pair<int, int> oneInning(int inning, int idx) {
int out = 0;
int score = 0;
vector<bool> base = {1,0,0,0};
while(out < 3) {
int hitter = seq[idx];
base[0] = true; //타자 투입
if (info[inning][hitter] == 0)
out++;
else
score += move(base, info[inning][hitter]);
idx = (idx + 1) % 9;
}
return { score, idx };
}
4. 타자의 n루타의 정보를 통해 점수를 얻을 수 있는 상황(next >= 4)에는 score를 획득하며, 아닌 경우에는 루의 위치를 변경시켜준다.
int move(vector<bool> &base, int scoretype) {
int score = 0;
for (int i = 3; i >= 0; i--) {
if (base[i]) {
int next = i + scoretype;
if (next >= 4) {
score++;
base[i] = false;
}
else {
base[next] = true;
base[i] = false;
}
}
}
return score;
}
소스 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool visited[9];
int seq[10];
int info[51][9];
int N;
int move(vector<bool> &base, int scoretype) {
int score = 0;
for (int i = 3; i >= 0; i--) {
if (base[i]) {
int next = i + scoretype;
if (next >= 4) {
score++;
base[i] = false;
}
else {
base[next] = true;
base[i] = false;
}
}
}
return score;
}
pair<int, int> oneInning(int inning, int idx) {
int out = 0;
int score = 0;
vector<bool> base = {1,0,0,0};
while(out < 3) {
int hitter = seq[idx];
base[0] = true; //타자 투입
if (info[inning][hitter] == 0)
out++;
else
score += move(base, info[inning][hitter]);
idx = (idx + 1) % 9;
}
return { score, idx };
}
int play_game() { //순서가 결정 되었을 때
int inning = -1;
int now = 0;
int sum = 0;
while (++inning < N) {
pair<int, int> info = oneInning(inning, now);
sum += info.first;
now = info.second;
}
return sum;
}
int solve(int cnt) {
int maximum = 0;
if (cnt == 3)
cnt++;
if (cnt == 9) {
return play_game();
}
for (int i = 0; i < 9; i++) {
if (!visited[i]) {
visited[i] = true;
seq[cnt] = i;
maximum = max(maximum, solve(cnt + 1));
visited[i] = false;
}
}
return maximum;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++)
for (int j = 0; j < 9; j++)
cin >> info[i][j];
visited[0] = true;
seq[3] = 0;
cout << solve(0);
}
이 문제는 사다리에 추가적으로 가로선을 0개 부터 최대 3개까지 놓는 가능한 모든 경우의 수를 다 보아야 해결 할 수 있다. 결국 조합 문제로 해석될 수 있으므로, 백트래킹을 하며 모든 조합에 대해 문제의 조건은 1번째부터 i번째에서 출발할 때 순서대로 1번째부터 i번째의 도착 지점에 도달하면 카운트하고, 그 카운트가 4이상이거나 가능한 방법이 없다면 -1을 출력하면 된다.
(1) 변수
map[h][l]는 h의 높이, l번째 라인이 h의 높이, l+1번째 라인에 가로선이 연결되어 있다면 1, 아니면 0으로 나타낸다.
(2) go() 함수
bool go() {
for (int i = 1; i <= N; i++) {
int nowl = i;
for (int nowh = 0; nowh <= H; nowh++){
if (map[nowh][nowl] == 1)
nowl++;
else if (map[nowh][nowl - 1] == 1)
nowl--;
}
if (nowl != i)
return false;
}
return true;
}
이 함수는 사다리의 출발지점과 도착지점이 같은지 따라가보는 함수이다.
모든 사다리의 출발지점 1~N에 대해 확인 하여야 하기 때문에 for문에서 경우를 검사해보자. 현재 출발 라인을 nowl = i 라 하고, nowh(0~H)를 따라갈때, 우측에 사다리가 있는 경우 (if(map[nowh][nowl] == 1)) 라인을 오른쪽으로 옮겨갈 것(nowl++)이고, 좌측에 사다리가 있는 경우(if(map[nowh][nowl - 1] == 1)) 라인을 왼쪽으로 옮겨갈 것(nowl--)이다.
(3) solve()함수
void solve(int cnt, int now_h, int now_l) {
if (go()) {
result = min(cnt, result);
return;
}
if (cnt == 3)
return;
for (int h = now_h; h <= H; h++) {
for (int l = now_l; l < N; l++) {
if (map[h][l] == 0 && map[h][l - 1] == 0 && map[h][l + 1] == 0) {
map[h][l] = 1;
solve(cnt + 1, h, l);
map[h][l] = 0;
}
}
now_l = 1;
}
}
이 함수는 조합을 보기 위한 백트래킹(DFS) 함수이다. 중복되는 경우를 보지 않기 위해 매게변수로(nowl, nowh)를 사용하였으며, 위 함수가 호출되는 모든 경우에 대해 위에 설명한 go()함수로 조건을 만족하는지 검사한다. cnt가 3보다 커지는 경우는 고려하지 않으므로 cnt는 3에서 return을 하게 된다.
가로선을 추가 할 수 있는 경우인,
양쪽에 가로라인이 존재하지 않을 때(if (map[h][l] == 0 && map[h][l - 1] == 0 && map[h][l + 1] == 0))
가로라인을 추가(map[h][l] = 1)하고, 함수를 진행 시킨뒤(solve(cnt + 1, h, 1)), 함수가 종료되면 해당 가로라인을 다시 삭제 (map[h][l] = 0)하면 된다.
소스 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, H;
int map[32][12]; //height, line
int result = 4;
bool go() {
for (int i = 1; i <= N; i++) {
int nowl = i;
for (int nowh = 0; nowh <= H; nowh++){
if (map[nowh][nowl] == 1)
nowl++;
else if (map[nowh][nowl - 1] == 1)
nowl--;
}
if (nowl != i)
return false;
}
return true;
}
void solve(int cnt, int now_h, int now_l) {
if (go()) {
result = min(cnt, result);
return;
}
if (cnt == 3)
return;
for (int h = now_h; h <= H; h++) {
for (int l = now_l; l < N; l++) {
if (map[h][l] == 0 && map[h][l - 1] == 0 && map[h][l + 1] == 0) {
map[h][l] = 1;
solve(cnt + 1, h, l);
map[h][l] = 0;
}
}
now_l = 1;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M >> H;
for (int i = 1; i <= M; i++) {
int a, b;
cin >> a >> b; //a높이 b라인
map[a][b] = 1;
}
solve(0, 1, 1);
if (result >= 4)
cout << -1 << "\n";
else
cout << result << "\n";
}
