문제
https://www.acmicpc.net/problem/2873
풀이
정답을 생각해 내기도 어렵고 생각했더라도 구현도 어려웠던 문제였다.
먼저 든 생각은 모든 칸을 다 지나야 가장 큰 기쁨을 얻는게 아닌가? 였다. 그래서 R과 C가 나올 수 있는 경우((홀수,홀수),(홀수,짝수),(짝수,홀수),(짝수,짝수))를 구해보고 그림을 그려보니 R과 C 둘중 하나가 홀수일때 모든 칸을 다 지날 수 있었다.
하지만 R과 C가 둘다 짝수인 경우에는 아무리 생각해봐도 모든 칸을 지나게 그릴 수 없었다.
그러면 한칸을 빼고는 다 지날 수 있을까? 라는 생각이 들어 한칸을 빼고 그려봤는데 어떨때는 가능하고 어떨때는 가능하지 않다는걸 발견하였다.
그러면 어떨때 한칸을 빼고 모든 칸을 지날 수 있는지만 안다면 답을 구할 수 있다는 뜻이 된다.
하지만 혼자서는 도저히 어떨때 빼는지 모르겠어서 다른 블로그들을 참고하였다.
짝수 * 짝수
RC 행렬을 체스판이라고 생각해보면 다음과 같이 나타낼 수 있다
4 4
O X O X
X O X O
O X O X
X O X O
여기서 잘 보면 시작점과 도착점은 둘다 O이다 즉, 시작점에서 도착점으로 갈때 방문한 칸들 중에서는
O가 X보다 많이 방문했다는 것을 뜻한다.
R과 C가 둘다 짝수이기 때문에 O로 시작해서 O로 도달할려면 X를 하나 방문하지 않으면 된다.
둘다 짝수일 때는 O의 갯수와 X의 갯수가 서로 같기 때문이다.
즉 X의 칸들중 가장 작은 기쁨을 갖는 칸을 제외하고 다른 칸을 모두 방문하면 된다.
하지만 여기까지 생각을 했더라도 이걸 어떻게 구현할지 막막하다.
짝수*짝수 경로 구하는 방법
(1)
먼저 제외할 칸을 구해준다 이걸 x,y로 두겠다.
int x = 0;
int y = 1;
for(int i=0; i<R; i++) {
for(int j=0; j<C; j++) {
if((i+j) % 2 != 0) {
if(map[x][y] > map[i][j]) {
x = i;
y = j;
}
}
}
}(2)
x,y를 구했다면 시작점과 도착점을 다음과 같이 초기화 해준다.
//시작점
int x1 = 0;
int y1 = 0;
//도착점
int x2 = R-1;
int y2 = C-1;시작점과 도착점을 동시에 출발시킨다. 양쪽에서 동시에 출발해서 서로 만난다면 시작점과 도착점이 지나온경로를 합친게 정답이 된다.
시작점과 도착점을 동시에 움직일때 각 점들은 두 행씩 움직이면서 두 점의 x좌표 차이가 1이 될때까지 반복해준다.
while(x2 - x1 > 1) {
...
}우리가 원하는 그림은 다음과 같이 두가지 그림으로 나타낼 수 있다.
첫번째 그림처럼 시작점이랑 제외할 칸의 행이 같을때, 두번째 그림처럼 도착점이랑 제외할 칸의 행이 같을떄로 나눌 수 있다.
즉, 다음과 같은 그림이 나올때까지 while문을 돌려줘야 한다.
먼저, 위 그림에서 알 수 있듯이 각 점과 제외할 점의 행을 서로 비교하면서 이동을 해야한다는 것을 알 수 있다. 그럼 언제 이동을 멈춰야 할까??
제외할 점의 행은 위 두가지 그림에서 알 수 있듯이 홀수이거나 짝수일 것이다.
홀수일때는 시작점의 행과 제외할 칸의 행이 같을때 시작점은 이동을 멈춰야하고, 도착점의 행과 제외할점의 행이 한칸 차이날때 이동을 멈춰야 한다.
짝수일때는 시작점의 행과 제외할 칸의 행이 한 칸 차이날때 이동을 멈춰야하고, 도착점의 행과 제외할점의 행이 같을때 이동을 멈춰야 한다.
이것을 더 생각해보면 제외할 칸의 행이 4라면 시작점은 3, 도착점은 4에서 멈춰야하고 이를 수식으로 나타내면 x1/2 가 x/2보다 작을때 이동을 할 수 있고, x2/2가 x/2보다 클때 이동이 가능하다.
두 점의 x좌표 차이가 1이 될때까지 반복해줬다면 이제는 두 점의 y좌표 차이가 1이 될때까지 반복해 준다.
그러면 다음과 같은 그림이 나오게 된다.
첫번째 그림과 같은 경우라면 밑으로 갔다가 오른쪽으로 가면되고,
두번째 그림과 같은 경우라묜 오른쪽으로 갔다가 밑으로 가면 된다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int R;
static int C;
static int[][] map;
static int[][] visit;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
String answer = "";
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new int[R][C];
for(int i=0; i<R; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<C; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
if(R % 2 != 0 || C % 2 != 0) {
// 홀 홀 | 홀 짝 | 짝 홀
if(R % 2 != 0) {
for(int i=1; i<=R; i++) {
for(int j=1; j<C; j++) {
if(i % 2 != 0) answer += "R";
else answer += "L";
}
if(i != R)answer += "D";
}
}else {
for(int i=1; i<=C; i++) {
for(int j=1; j<R; j++) {
if(i % 2 != 0) answer += "D";
else answer += "U";
}
if(i != C)answer += "R";
}
}
System.out.println(answer);
}else {
// 짝 짝
int x = 0;
int y = 1;
for(int i=0; i<R; i++) {
for(int j=0; j<C; j++) {
if((i+j) % 2 != 0) {
if(map[x][y] > map[i][j]) {
x = i;
y = j;
}
}
}
}
int x1 = 0;
int y1 = 0;
int x2 = R-1;
int y2 = C-1;
StringBuilder s1 = new StringBuilder();
StringBuilder s2 = new StringBuilder();
while(x2 - x1 > 1) {
if(x1/2 < x/2) {
append(s1, 'R', C-1);
append(s1, 'D', 1);
append(s1, 'L', C-1);
append(s1, 'D', 1);
x1+=2;
}
if(x/2 < x2/2) {
append(s2, 'R', C-1);
append(s2, 'D', 1);
append(s2, 'L', C-1);
append(s2, 'D', 1);
x2-=2;
}
}
while(y2 - y1 > 1) {
if(y1/2 < y/2) {
append(s1, 'D', 1);
append(s1, 'R', 1);
append(s1, 'U', 1);
append(s1, 'R', 1);
y1+=2;
}
if(y/2 < y2/2) {
append(s2, 'D', 1);
append(s2, 'R', 1);
append(s2, 'U', 1);
append(s2, 'R', 1);
y2-=2;
}
}
if(y == y1) {
append(s1, 'R', 1);
append(s1, 'D', 1);
}else {
append(s1, 'D', 1);
append(s1, 'R', 1);
}
s2.reverse();
s1.append(s2);
System.out.println(s1);
}
}
public static void append(StringBuilder s,char c, int cnt) {
for(int i=0; i<cnt; i++)
s.append(c);
}
}