본문으로 바로가기
  • 맵의 가로나 세로 중 하나라도 홀수인 경우 모든 점을 다 지날 수 있다.
  • 맵의 가로와 세로가 짝수라면 최소 한 점은 지날 수 없다.
  • 맵을 체스판이라 보고 가장 왼쪽을 흰점이라 했을 때 흑점 하나는 반드시 지날 수 없게 된다.
  • 흑점 중 가장 기쁨이 낮은 점을 설정하고 해당 지점을 피해서 목적지까지 도착한다.
#include <cstdio>
#include <string>
using namespace std;

int r, c;
int map[1000][1000];
pair<int, int> p;
string path;

int main() {
  scanf("%d %d", &r, &c);

  // r이나 c가 홀수이면 항상 길이 있다
  if (r%2 == 1) {
    for (int i=0; i<r; i++) {
      for (int j=0; j<c-1; j++) {
        path += i%2 == 0 ? 'R' : 'L';
      }
      if (i != r-1) path += 'D';
    }
  }
  // r이나 c가 홀수이면 항상 길이 있다
  else if (c%2 == 1) {
    for (int i=0; i<c; i++) {
      for (int j=0; j<r-1; j++) {
        path += i%2 == 0 ? 'D' : 'U';
      }
      if (i != c-1) path += 'R';
    }
  }
  // r과 c가 모두 짝수인 경우 최소 하나를 지나갈 수 없다
  else {
    int tmp = 1000;
    for (int i=0; i<r; i++) {
      for (int j=0; j<c; j++) {
        scanf("%d", &map[i][j]);
        // (0, 0)을 체스판의 흰점이라 했을 때, 검은 점 하나는 반드시 지날 수 없다
        if ((i%2 == 0 && j%2 == 1) || (i%2 == 1 && j%2 == 0)) {
          // 기쁨이 가장 낮은 점을 지나지 말아야 할 좌표로 설정한다
          if (map[i][j] < tmp) {
            tmp = map[i][j];
            p = {i, j};
          }
        }
      }
    }

    // 지나지 말아야 할 좌표의 맨 왼쪽으로 내려온 다음
    int nr = (p.first/2) * 2;
    for (int i=0; i<nr; i++) {
      for (int j=0; j<c-1; j++) {
        path += i%2 == 0 ? 'R' : 'L';
      }
      path += 'D';
    }

    // 좌표의 대각선 아래까지 이동하고
    int nc = p.second;
    for (int i=0; i<nc; i++) {
      path += i%2 == 0 ? "DR" : "UR";
    }

    // 좌표의 우측 끝으로 이동한 다음
    for (int i=nc; i<c-1; i++) {
      path += i%2 == 0 ? "RD" : "RU";
    }

    // 목적지까지 간다
    int mr = r - (p.first % 2 == 0 ? p.first+2 : p.first+1);
    for (int i=0; i<mr; i++) {
      path += 'D';
      for (int j=0; j<c-1; j++) {
        path += i%2 == 0 ? 'L' : 'R';
      }
    }
  }

  printf("%s\n", path.c_str());
  return 0;
}

'Programming > Baekjoon Online Judge' 카테고리의 다른 글

[BOJ] 1780: 종이의 개수  (0) 2018.07.03
[BOJ] 11728: 배열 합치기  (0) 2018.07.03
[BOJ] 2873: 롤러코스터  (1) 2018.07.03
[BOJ] 1080: 행렬  (0) 2018.07.02
[BOJ] 1201: NMK  (0) 2018.07.02
[BOJ] 10610: 30  (0) 2018.07.02

댓글을 달아 주세요

  1. Favicon of https://blog.naver.com/lmj3322 Yumin 2018.12.28 21:33 신고

    많은 도움이 되었습니다.