완전 탐색을 하면 안되는 이유?
이 문제의 최대 행과 열은 1000이다, 2차원 배열의 한 원소에서 최대 4가지 방향으로 나아갈 수 있다. 방문 배열을 제외한다고 치더라도, (N - @) ^ 1000 * 1000이므로 TLE가 발생할 수 밖에 없다.
가장 기쁨 누적치가 크게 하려면?
최대한 많은 원소들을 방문하면 된다. 그렇다면, 풀스캔으로 모든 노드들을 볼 수 있을까? 스스로 예제를 만들어 문제를 관찰해보자.
행이 홀 수거나 열이 홀 수 일 때
위의 두 그림처럼, 배열에 적힌 숫자의 순서로 모든 원소들을 방문할 수 있다.
행과 열이 모두 짝 수 일 때
스스로 예제를 만들어보면 알겠지만, 행과 열이 모두 짝수일 때는 문제가 발생한다.
위의 그림처럼, 차례대로 스캔해서 내려오면 아래의 마지막 줄은 모두 방문하지 못하게 된다.
아래의 마지막 줄도 방문할 수 있도록 경로를 수정해주면 어떨까?
마지막 줄도 방문되려면, 어떤 순간에 한 줄씩 내려가는게 아니라 두 줄씩 내려가는게 필요하다.
하나의 원소를 방문하지 않으면 어떻게 될까?
위의 두 그림을 보면, 하나의 원소를 방문하지 않고 두 줄을 동시에 방문하면, 중간에 경로의 순서가 바껴 마지막 줄까지 방문이 될 것을 추측할 수 있다.
하나의 원소를 어떻게 지정할까?
어떤 행에서든 발생할 수 있지만, 임의의 열에 대해서 적용이 되는 것은 아니다. 짝수 행은 홀수 열만, 홀수 행은 짝수 열만 가능하다.
경로를 그리다 보면 직관적으로 감이 올 것이다.조건을 만족하는 가장 작은 수를 빼고 방문하면 된다.
코드 구현 방식?
방문하지 않은 원소를 가진 행 혹은 근접 행을 제외하고는 위에서부터 오른쪽으로 스캔하면 된다.
출발지와 목적지에 대한 행, 열 정보를 이용해 탐색 구간을 좁혀가면서, 방문 순서를 채워가면 된다.
JAVA 코드
import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
static BufferedReader br;
static BufferedWriter bw;
static StringBuilder sb;
static StringBuilder rsb;
static int[][] map;
static int R, C;
public static void main (String[] args) throws java.lang.Exception
{
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
sb = new StringBuilder("");
rsb = new StringBuilder("");
String[] sArr;
sArr = br.readLine().split(" ");
R = Integer.valueOf(sArr[0]);
C = Integer.valueOf(sArr[1]);
map = new int[R][C];
for(int i = 0; i < R; i++){
sArr = br.readLine().split(" ");
for(int j = 0; j < sArr.length; j++){
map[i][j] = Integer.valueOf(sArr[j]);
}
}
if(R % 2 == 1){
for(int i = 0; i < R; i++){
if(i % 2 == 0){
for(int j = 0; j < C - 1; j++) sb.append("R");
}else{
for(int j = 0; j < C - 1; j++) sb.append("L");
}
if(i != R - 1)
sb.append("D");
}
bw.write(sb.toString() + "\n");
bw.flush();
}else if(C % 2 == 1){
for(int i = 0; i < C; i++){
if(i % 2 == 0){
for(int j = 0; j < R - 1; j++) sb.append("D");
}else{
for(int j = 0; j < R - 1; j++) sb.append("U");
}
if(i != C - 1)
sb.append("R");
}
bw.write(sb.toString() + "\n");
bw.flush();
}else{
int mr = -1, mc = -1;
int val = Integer.MAX_VALUE;
for(int i = 0; i < R; i++){
if(i % 2 == 0){
for(int j = 1; j < C; j += 2){
if(map[i][j] < val){
val = map[i][j]; mr = i; mc = j;
}
}
}else{
for(int j = 0; j < C; j += 2){
if(map[i][j] < val){
val = map[i][j]; mr = i; mc = j;
}
}
}
}
int r1 = 0, c1 = 0, r2 = R - 1, c2 = C - 1;
while(r2 - r1 > 1){
if(mr - r1 > 1){
for(int j = 0; j < C - 1; j++) sb.append("R");
sb.append("D");
for(int j = 0; j < C - 1; j++) sb.append("L");
sb.append("D");
r1 += 2;
}
if(r2 - mr > 1){
for(int j = 0; j < C - 1; j++) rsb.append("R");
rsb.append("D");
for(int j = 0; j < C - 1; j++) rsb.append("L");
rsb.append("D");
r2 -= 2;
}
}
while(c2 - c1 > 1){
if(mc - c1 > 1){
sb.append("D");
sb.append("R");
sb.append("U");
sb.append("R");
c1 += 2;
}
if(c2 - mc > 1){
rsb.append("D");
rsb.append("R");
rsb.append("U");
rsb.append("R");
c2 -= 2;
}
}
if(r1 + 1 == mr){
sb.append("R");
sb.append("D");
}else if(r2 - 1 == mr){
sb.append("D");
sb.append("R");
}
sb.append(rsb.reverse());
bw.write(sb.toString() + "\n");
bw.flush();
}
}
}