삼성 SW 역량 테스트 기출 문제 풀이

14503 로봇 청소기

문제 링크

문제 접근

0 인 경우 청소되지 않은 빈 칸이고, 1 인 경우 벽이 있는 것이고 방의 가장 북,남,서,동쪽에 위치한 모든 칸에는 벽으로 테두리가 쳐져있다.

특이한 점은 로봇청소기의 회전이 반시계라고 정해져있고 로봇청소기의 방향 d 가 시계방향으로 북-동-남-서 가 1-2-3-4 라는 점이다.

특정 조건을 만족하는 한 계속 이동한다는 것은 while, 조건을 만족하지 않으면 break로 빠져나오는 것을 활용할 수도 있다.

4방향으로 탐색을 먼저 수행하는데

• 빈칸이 있을 경우에만 이동하고
• 탐색이 안된다면, 뒤로 한칸 가서 반복한다.

풀이

• 프로그램 작동 방식: 갈 수 있는 곳까지 가다가, 가로막히면 후진, 후진을 하지 못하면 종료한다.
• 현재 위치에서 DFS로 청소하다가, 막히면 후진, 후진하려는 곳이 벽이면 종료한다.
• 방향이 있을 땐 항상 dy, dx 를 선언해준다.

// 시계 방향으로
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

시간복잡도

O(N*M)

자료구조

• 전체 지도 : int[][]
• 내 위치, 방향, 청소하는 칸 : int y , int x , int d , int cnt

전체 코드

#include<iostream>
using namespace std;
int map[50][50];
int visited[50][50];
int n,m;

int dr[4] = {-1, 0, 1, 0}; // direction of Y
int dc[4] = {0, 1, 0, -1}; // direction of X

void dfs(int r, int c, int d, int sum){
/*
1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
	a.왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
	b.왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
	c.네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
	d.네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
*/

	for(int i = 0; i < 4; i++){ 
    	inf nd = (d + 3 - i) % 4; // 반시계 방향 (북-동-남-서)
        int nr = r + dr[nd];
        int nc = c + dc[nd];
        
        if(nr < 0 || nr >= n || nc < 0 || nc >= m || map[nr][nc] == 1) {  
        	// 범위를 넘어가거나 벽이면 다음 방향으로 스킵
            continue;
        }
        
        //a. 아직 청소하지 않은 공간이 존재한다면
        if(visited[nr][nc] == 0 && map[nr][nc] == 0){
               visited[nr][nc] = 1; //현재 위치 청소
               dfs(nr, nc, nd, sum+1);
           }
    }
	
    int backIdx = d+2 < 4 ? d+2 : d-2;
    int backr = r + dr[backIdx];
    int backc = c + dc[backIdx];
    if(0 <= backr && backr <= n && 0 <= backc && backc <= m){
        if(map[backr][backc] == 0){   //뒤쪽 방햑 벽 아니어서 후진할 수 있을 때
            dfs(backr, backc, d, sum);  //한칸 후진
        }
        else{   //뒤쪽 방향 벽이라 후진 못할 때
            cout << sum <<'\n';
            exit(0);
        }
    }
}

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int r,c,d;
  	cin >> n, m;
    cin >> r >> c >> d;
    
    for(int i=0; i<n; i++){
    	for(int j=0; j<m; j++){
        	cin >> map[i][j];
            visited[i][j]=0;
        }
    }
    
    visited[r][c]=1;
    dfs(r,c,d,1);
    
    return 0;
}

exit()

break 는 반복문이나 스위치문, return 은 함수, exit 는 프로그램 단위로 제어을 하는 것이다.
exit 문은 보통 exit(0) , exit(1) 이 두가지 형태로 많이 쓰는데 프로그램 수행이 정상적으로 종료 된다면 0을 비정상적이면 1 이나 0 이 아닌 기타 정수를 쓴다. 즉 exit는 프로그램에 그 값을 리턴하고 종료하는 기능을 하죠. 함수라면 몰라도 프로그램 자체가 어떤값을 리턴 받을 필요가 있을까 생각이 들 수 있지만 특수한 경우프로그램이 정상적인 수행이 됐는지를 알아보기 위해 사용되기도 한다고 한다.

그러면 main 함수에서 리턴문은 특별한 의미가 있을까?

리턴을 함수를 끝내는 명령이니 메인에서 쓰였다면 exit 랑 동급의 기능을 하겠다. 즉 프로그램 실행을 종료시기는 기능을 하게된다.