문제 링크
알고리즘: 그리디 알고리즘, 구현
문제
상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다.
어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다.
이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착할 것이다. 롤러코스터는 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동할 수 있다. 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다.
각 칸에는 그 칸을 지나갈 때, 탑승자가 얻을 수 있는 기쁨을 나타낸 숫자가 적혀있다. 롤러코스터를 탄 사람이 얻을 수 있는 기쁨은 지나간 칸의 기쁨의 합이다. 가장 큰 기쁨을 주는 롤러코스터는 어떻게 움직여야 하는지를 구하는 프로그램을 작성하시오.
풀이
3개의 case로 나눌 수 있다.
1.R이 홀수인 경우
모든 칸을 지나갈 수 있다.
2.C가 홀수인 경우
모든 칸을 지나갈 수 있다.
3.R,C 둘 다 짝수인 경우
x,y 좌표가 홀 짝이거나 짝 홀인 좌표 중에 하나를 제외하면 모든 칸을 지나갈 수 있다. (그리디)
제일 작은 기쁨을 가진 칸을 제외한다.
그리고 출발지부터 도착지까지 연결하면 된다.
이 case 루트의 특징은 (제외된 칸의 행 + 제외된 칸 행 + 1) or (제외된 칸 행+ 제외된 칸 행 - 1) 의 두 행은 지그재그의 형태로 칸을 지나가고, 나머지는 행들은 ㄹ자 형태로 통일된다.
이 문제의 솔루션은 쉽게 찾았지만, 구현에서 오래 걸렸다. 개인적인 느낌상 구현 70% 그리디 30% 정도의 문제인 것 같다.
자바로 풀 때 주의할 점은 ans의 타입을 절대로 String으로 선언하면 안 된다. 그 이유는 String은 +연산을 할 때마다 새로 할당하고 붙이고 이 과정을 반복하기 때문에 StringBuilder로 선언하고 append로 문자를 연결해야 시간 초과 없이 풀 수 있다. => 이거 하나 때문에 다 구현하고도 시간 초과가 발생해 많이 헤맸다..
소스 코드
import java.io.*;
import java.util.*;
class Coordinate {
int x,y;
Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int R,C;
static Coordinate min = new Coordinate(-1,-1);
static int map[][];
static StringBuilder ans = new StringBuilder();
static boolean last_ex = false;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new int[R][C];
for(int i=0; i<R; i++) {
StringTokenizer sti = new StringTokenizer(br.readLine());
for(int j=0; j<C; j++) {
map[i][j] = Integer.parseInt(sti.nextToken());
if((i%2==1 && j%2==0) || (i%2==0 && j%2==1)) {
if(min.x == -1) {
min = new Coordinate(j,i);
} else {
if(map[min.y][min.x] > map[i][j]) {
min = new Coordinate(j,i);
}
}
}
}
}
if(min.y == R-1) {
min = new Coordinate(min.x+1, min.y);
last_ex = true;
} else {
min = new Coordinate(min.x+1, min.y+1);
}
if(R%2==1) {
for(int i=1; i<=R; i++) {
for(int j=1; j<=C; j++) {
if(i!=R || j!=C) {
if(i%2==1) {
if(j==C) {
ans.append("D");
} else {
ans.append("R");
}
} else {
if(j==C) {
ans.append("D");
} else {
ans.append("L");
}
}
}
}
}
} else if(C%2==1) {
for(int i=1; i<=C; i++) {
for(int j=1; j<=R; j++) {
if(i!=C || j!=R) {
if(i%2==1) {
if(j==R) {
ans.append("R");
} else {
ans.append("D");
}
} else {
if(j==R) {
ans.append("R");
} else {
ans.append("U");
}
}
}
}
}
} else {
//둘다 짝수면
String zigzag_1,zigzag_2,c1_zigzag,c2_zigzag;
char zad; //zigzag after direction
char d = 'R';
boolean toggle = true;
if(min.y % 2 == 1) {
zad = 'L';
zigzag_1 = "DR";
zigzag_2 = "UR";
if(last_ex) {
c1_zigzag = "RD";
c2_zigzag = "RU";
} else {
c1_zigzag = "RU";
c2_zigzag = "RD";
}
} else {
min.x = C+1-min.x;
zad = 'R';
zigzag_1 = "DL";
zigzag_2 = "UL";
c1_zigzag = "LU";
c2_zigzag = "LD";
}
//반대 세팅
for(int i=1; i<=R-1; i++) {
for(int j=1; j<=C; j++) {
if(i!=R-1 || j!=C) {
if(i==min.y) {
if(j==min.x) {
if(j==C) {
ans.append("D");
d = zad;
} else {
zigzag_1 = c1_zigzag;
zigzag_2 = c2_zigzag;
ans.append(zigzag_1);
toggle = false;
}
} else {
if(j==C) {
ans.append("D");
d = zad;
} else {
if(toggle) {
ans.append(zigzag_1);
toggle = false;
} else {
ans.append(zigzag_2);
toggle = true;
}
}
}
} else {
if(d=='R') {
if(j==C) {
ans.append("D");
d='L';
} else {
ans.append("R");
}
} else if(d=='L') {
if(j==C) {
ans.append("D");
d='R';
} else {
ans.append("L");
}
}
}
}
}
}
}
System.out.println(ans);
}
}