NYPC 2022 Round 2-A | 로봇 청소기

[문제]

 

N×M 크기의 격자 모양 마루가 있다.

위에서부터 R째 행, 왼쪽에서부터 C번째 열에 있는 마루의 칸은 (R,C)로 나타낸다.

마루는 자주 더러워지기 때문에 평소 관리를 위해 로봇 청소기를 사용하고 있다.

로봇 청소기가 청소를 시작하면 첫 행의 임의의 칸에서 출발하여, 이동하면서 지나가는 칸을 모두 청소한다.

그렇게 첫 행에서 출발하여 마지막 행에 도착하면 한 번의 청소를 끝낸 것이다.

로봇 청소기가 격자 위를 이동하는 방법은 L, D, R의 세 가지인데, 로봇 청소기의 현재 위치가 (r,c)라면

• L은 (R+1,C−1)로 이동하는 것이다. 단, 해당하는 칸이 존재해야 한다.
• D는 (R+1,C)로 이동하는 것이다.
• R은 (R+1,C+1)로 이동하는 것이다. 단, 해당하는 칸이 존재해야 한다.

각 방법에 따른 로봇 청소기의 이동 위치를 그림으로 나타내면 다음과 같다.

[그림 1]

지금 반드시 청소가 필요한 칸에 X 표시가 되어있어서, 로봇 청소기는 청소해야 하는 칸들을 모두 한 번 이상 청소할 때까지 청소를 반복한다.

아래 그림은 4×54×5 크기의 격자 모양 마루에서 로봇 청소기가 어떻게 청소하는지에 대한 예시를 보여준다. 이 경우, X 표시가 된 곳을 모두 청소하기 위해서는 로봇이 두 번 청소해야 함을 알 수 있다.

 

[그림 2]

격자에 대한 정보가 주어진다.

로봇 청소기가 청소해야 하는 최소 횟수를 구하고, 실제로 어떤 과정을 거쳐 청소해야 하는지 구하는 프로그램을 작성하시오.

 

 

[입력 형식]

 

첫 줄에 격자의 크기를 나타내는 두 정수 N과 M이 공백으로 구분되어 주어진다.

(2≤N,M; N×M≤1000000)

이어지는 N줄의 각 줄에 길이가 M인 문자열이 주어지는데, 이 문자열은 O와 X로만 구성되어 있고, X는 그 칸이 청소가 필요한 칸임을 나타낸다.

 

 

[출력 형식]

 

첫 줄에 로봇이 청소해야 하는 최소 횟수 K를 출력한다.

이어지는 K 줄의 각 줄에는 실제로 청소하는 과정을 출력한다.

한 번의 과정은 로봇이 첫 행에서 이동을 시작한 열의 번호 c (1≤c≤M)와 L, D, R로 구성된 길이 N−1인 문자열로 이동 방법을 순서대로 나타내야 한다.

만약 답이 여러 가지인 경우, 그중 아무거나 하나 출력한다.

 

 

[해설]

 

@myungwoo님의 블로그를 참고하고 풀어서 별도의 해설은 첨부하지 않겠습니다.

 

 

[C/C++ 코드]

 

#include<bits/stdc++.h>
using namespace std;

int n,m;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    char a[n+1][m+2];
    for(int i=1;i<=n;i++){
    	cin>>(a[i]+1);
	}
    vector<int>arr,init;
    vector<pair<int,int>>pos;
    vector<string>path;
    for (int i=1-m;i<=n-1;i++){
        int r=1,c=r-i;
        if(c<1){
        	r+=1-c;
        	c=1;
		}
        for(;r<=n&&c<=m;r++,c++){
            if(a[r][c]!='X'){
            	continue;
			}
            int v=-(r+c);
            auto it=lower_bound(begin(arr),end(arr),v);
            if(it==end(arr)){
                arr.push_back(v);
                pos.emplace_back(r,c);
                init.push_back(c);
                path.emplace_back(r-1,'D');
            }
            else{
                int i=it-begin(arr);
                arr[i]=v;
                int dr=r-pos[i].first;
                int dc=c-pos[i].second;
                pos[i]={r,c};
                if(dc<0){
                	path[i]+=string(-dc,'L');
				}
                else{
                	path[i]+=string(dc,'R');
				}
                path[i]+=string(dr-abs(dc),'D');
            }
        }
    }
    int k=size(arr);
    cout<<k<<'\n';
    for(int i=0;i<k;i++){
        path[i]+=string(n-pos[i].first,'D');
        cout<<init[i]<<' '<<path[i]<<'\n';
    }
}