백준 14503번 - 로봇 청소기

 

https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

알고리즘 분석

 

해당 문제는 재귀함수(recursive function)를 사용하는 대표적인 문제이다.

 

예를 들어 아래와 같은 5x5 matrix 가 주어졌다고 해보자.

 

아래에서 화살표 표시가 된 곳이 로봇청소기가 처음으로 위치하는 자리가 된다.

 

그리고 초기에 청소기가 바라보는 방향은 북쪽이라고 가정하자.

 

(빈칸을 0 벽을 1 청소가 된 칸을 2로 가정하자.)

 

첫 번째로 로봇은 현재위치를 청소할 것이다.

 

그리고 자신이 바라보는 방향의 왼쪽으로 방향을 틀 것이다.

 

그럼 아래와 같은 형태가 된다.

위의 그림의 방향으로 로봇이 직진한 다음 해당 구역도 청소를 해준다.

 

그리고 현재방향의 왼쪽 방향을 바라봐준다.

로봇이 방향을 왼쪽으로 틀었지만,

 

현재 벽을 바라보고 있으므로 또 왼쪽으로 방향을 틀어준다.

하지만, 이번에도 이미 청소한 곳이므로 다시 현재방향의 왼쪽으로 틀어준다.

방향을 틀었음에도 불구하고 또 벽이 나와서 앞으로 갈 수 없다.

 

이번에도 다시 왼쪽으로 방향을 틀어준다.

 

로봇이 바라보는 방향에는 어떠한 장애물도 없고 아직 청소가 된 구역이 아니기 때문에

 

해당 구역으로 이동하여 청소해준다.

같은 논리대로 계속 진행해 주면 아래의 그림과 같이 완성이 될 것이다.

 

이제 4면 어디에도 청소를 하지 않은 공간은 존재하지 않는다.

 

이럴 경우에는 뒤에 벽이 아니라면 후진을 해준다.

이번에도 후진을 해준다.

이러한 상황에서 로봇은 4면 어디에도 청소하지 않은 공간이 없고,

 

후면에는 벽이 막힌 상황을 인지하고 시동을 종료하게 된다.

 

즉 청소한 구간은 총 5개의 구간이 된다.

 

 

방향데이터는 아래와 같이 쓸 수 있다.

 

 

 

만약에 현재 로봇의 위치가 (3,3)이고 방향이 북쪽(0)이라고 가정하면,

 

주어진 문제의 조건에 의하여 방향데이터는 서쪽(3)으로 바꾸어야 하며,

 

진행하는 방향은 (3,2)가 되어야 한다. 그리고 해당 (3,2)를 방문하여

 

청소했다는 표시를 남겨주고 카운트를 늘려주는 로직을 작성하면 된다.

 

이 문제는 방향데이터를 어떤 식으로 다루느냐가 중요한데,

 

반시계 방향으로 돌아가는 로직과, 후진하는 로직이 중요하다.

 

위 그림을 보면 Direction list 가 있는데, 각 방향인덱스마다

 

벡터가 존재하는 모습을 보인다. (예를 들어 북[0]인 경우 벡터는 {-1,0})

 

반시계 방향으로 회전하는 로직 같은 경우에는

 

동[1] -> 북[0]으로 변화하는 모습을 볼 수 있다. 

 

즉 이 경우에는 next_index = (index + 3) % 4라고 볼 수 있다.

 

(다른 경우에도 직접 계산을 해보길 바란다.)

 

후진하는 로직 같은 경우에는 

 

동[1] -> 서[3]로 변화하고 있다.

 

즉 이 경우에는 next_index = (index + 2) % 4로 표현할 수 있다.

 

 

 

 

 

 

알고리즘 구현

 

C++

1. 재귀함수를 통한 DFS 구현

#include <iostream>
#include <stack>

using namespace std;

int N,M,c,r,v;
int cleanCnt;
int map[51][51];
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};

int backTurn(int v)
{
    int backV = (v + 2) % 4;
    return backV;
}

int leftTurn(int v)
{
    int leftV = (v + 3) % 4;
    return leftV;
}

void dfs(int r, int c, int v, int plus)
{   
    if (plus == 1)
    {
        cleanCnt++;
        map[r][c] = 2;
    }
    
    bool flag = false;

    for (int i = 0; i < 4; i++)
    {
        int newR = r + dr[i];
        int newC = c + dc[i];

        if (map[newR][newC] == 0)
        {
            flag = true;
            break;
        }
    }
    
    if (flag)
    {
        int leftV = leftTurn(v);

        int newR = r + dr[leftV];
        int newC = c + dc[leftV];   

        if (map[newR][newC] == 0) dfs(newR, newC, leftV, 1);
        else dfs(r, c, leftV, 0);
    }
    else
    {
        int backV = backTurn(v);
        int backR = r + dr[backV];
        int backC = c + dc[backV];

        if (map[backR][backC] != 1) dfs(backR, backC, v, 0);
    }

    return;
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> N >> M >> r >> c >> v;

    for (int i = 0; i < N*M; i++) cin >> map[i/M][i%M];
    
    dfs(r,c,v,1);
    
    cout << cleanCnt << endl;

    return 0;
}

 

2. Stack을 사용한 DFS 구현

#include <iostream>
#include <stack>

using namespace std;

int N,M,c,r,v;
int cleanCnt;
int map[51][51];
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};

struct Elem {
    int r,c,v,p;
};

int backTurn(int v)
{
    int backV = (v + 2) % 4;
    return backV;
}

int leftTurn(int v)
{
    int leftV = (v + 3) % 4;
    return leftV;
}

void dfs(int r, int c, int v, int p)
{   
    
    stack<Elem> stack;
    stack.push({r, c, v, p});

    while(!stack.empty())
    {
        Elem elem = stack.top();
        stack.pop();

        if (elem.p == 1)
        {
            cleanCnt++;
            map[elem.r][elem.c] = 2; 
        }

        bool flag = false;

        for (int i = 0; i < 4; i++)
        {
            int newR = elem.r + dr[i];
            int newC = elem.c + dc[i];

            if (map[newR][newC] == 0)
            {
                flag = true;
                break;
            }
        }

        if (flag)
        {
            int leftV = leftTurn(elem.v);

            int newR = elem.r + dr[leftV];
            int newC = elem.c + dc[leftV];   

            if (map[newR][newC] == 0) stack.push({newR, newC, leftV, 1});
            else stack.push({elem.r, elem.c, leftV, 0});
        }
        else
        {
            int backV = backTurn(elem.v);
            int backR = elem.r + dr[backV];
            int backC = elem.c + dc[backV];

            if (map[backR][backC] != 1) stack.push({backR, backC, elem.v, 0});
        }
    }
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> N >> M >> r >> c >> v;

    for (int i = 0; i < N*M; i++) cin >> map[i/M][i%M];
    
    dfs(r,c,v,1);
    
    cout << cleanCnt << endl;

    return 0;
}

 

3. BFS 구현

#include <iostream>
#include <queue>

using namespace std;

int N,M,c,r,v;
int cleanCnt;
int map[51][51];
int dr[4] = {-1,0,1,0};
int dc[4] = {0,1,0,-1};

struct Elem {
    int r,c,v,p;
};

int backTurn(int v)
{
    int backV = (v + 2) % 4;
    return backV;
}

int leftTurn(int v)
{
    int leftV = (v + 3) % 4;
    return leftV;
}

void bfs(int r, int c, int v, int p)
{   
    
    queue<Elem> queue;
    queue.push({r, c, v, p});

    while(!queue.empty())
    {
        Elem elem = queue.front();
        queue.pop();

        if (elem.p == 1)
        {
            cleanCnt++;
            map[elem.r][elem.c] = 2; 
        }

        bool flag = false;

        for (int i = 0; i < 4; i++)
        {
            int newR = elem.r + dr[i];
            int newC = elem.c + dc[i];

            if (map[newR][newC] == 0)
            {
                flag = true;
                break;
            }
        }

        if (flag)
        {
            int leftV = leftTurn(elem.v);

            int newR = elem.r + dr[leftV];
            int newC = elem.c + dc[leftV];   

            if (map[newR][newC] == 0) queue.push({newR, newC, leftV, 1});
            else queue.push({elem.r, elem.c, leftV, 0});
        }
        else
        {
            int backV = backTurn(elem.v);
            int backR = elem.r + dr[backV];
            int backC = elem.c + dc[backV];

            if (map[backR][backC] != 1) queue.push({backR, backC, elem.v, 0});
        }
    }
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> N >> M >> r >> c >> v;

    for (int i = 0; i < N*M; i++) cin >> map[i/M][i%M];
    
    bfs(r,c,v,1);
    
    cout << cleanCnt << endl;

    return 0;
}

 

 

 

Java

 

1. 재귀함수를 통한 DFS 구현

import java.io.*;
import java.util.*;

public class Main {
    
    static int N,M,R,C,V;
    static int[] dr = {-1,0,1,0};    
    static int[] dc = {0,1,0,-1};
    static int[][] map;
    static int cleanCnt;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(stk.nextToken());        
        M = Integer.parseInt(stk.nextToken());

        map = new int[N][M];
        
        stk = new StringTokenizer(br.readLine(), " ");
        R = Integer.parseInt(stk.nextToken());        
        C = Integer.parseInt(stk.nextToken());
        V = Integer.parseInt(stk.nextToken());

        for (int i = 0; i < N; i++) {
            stk = new StringTokenizer(br.readLine(), " ");

            for (int j = 0; j < M; j++) map[i][j] = Integer.parseInt(stk.nextToken());
        }
        
        dfs(R,C,V,1);

        bw.write(cleanCnt + "");
        bw.flush();
        bw.close();
        br.close();
    }

    static void dfs(int r, int c, int v, int p) {
        
        if (p == 1) {
            map[r][c] = 2;
            cleanCnt++;
        }

        boolean flag = false;

        for (int i = 0; i < 4; i++) {
            int newR = r + dr[i];
            int newC = c + dc[i];

            if (map[newR][newC] == 0)
            {
                flag = true;
                break;
            }
        }

        if (flag) {
            int frontV = leftTurn(v);

            int frontR = r + dr[frontV];
            int frontC = c + dc[frontV];

            if (map[frontR][frontC] == 0) dfs(frontR, frontC, frontV, 1);
            else dfs(r,c,frontV,0);

        } else {

            int backV = backTurn(v);

            int backR = r + dr[backV];
            int backC = c + dc[backV];
            
            if (map[backR][backC] != 1) dfs(backR, backC, v, 0); 
        }

        return;
    }
    
    static int backTurn(int v) {
        int newV = (v + 2) % 4;
        return newV; 
    }

    static int leftTurn(int v)
    {
        int newV = (v + 3) % 4;
        return newV;
    }
}

 

 

2. Stack 을 사용한 DFS 구현

import java.io.*;
import java.util.*;

public class Main {
    
    static int N,M,R,C,V;
    static int[] dr = {-1,0,1,0};    
    static int[] dc = {0,1,0,-1};
    static int[][] map;
    static int cleanCnt;

    static class Elem {
        public int r,c,v,p;

        public Elem(int r, int c, int v, int p) {
            this.r = r;
            this.c = c;
            this.v = v;
            this.p = p;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(stk.nextToken());        
        M = Integer.parseInt(stk.nextToken());

        map = new int[N][M];
        
        stk = new StringTokenizer(br.readLine(), " ");
        R = Integer.parseInt(stk.nextToken());        
        C = Integer.parseInt(stk.nextToken());
        V = Integer.parseInt(stk.nextToken());

        for (int i = 0; i < N; i++) {
            stk = new StringTokenizer(br.readLine(), " ");

            for (int j = 0; j < M; j++) map[i][j] = Integer.parseInt(stk.nextToken());
        }
        
        dfs(R,C,V,1);

        bw.write(cleanCnt + "");
        bw.flush();
        bw.close();
        br.close();
    }

    static void dfs(int r, int c, int v, int p) {
        
        Stack<Elem> stack = new Stack<>();
        stack.push(new Elem(r,c,v,p));

        while(!stack.isEmpty()) {
            
            Elem elem = stack.peek();
            stack.pop();
            
            if (elem.p == 1) {
                map[elem.r][elem.c] = 2;
                cleanCnt++;
            }
    
            boolean flag = false;
    
            for (int i = 0; i < 4; i++) {
                int newR = elem.r + dr[i];
                int newC = elem.c + dc[i];
    
                if (map[newR][newC] == 0)
                {
                    flag = true;
                    break;
                }
            }
    
            if (flag) {
                int frontV = leftTurn(elem.v);
    
                int frontR = elem.r + dr[frontV];
                int frontC = elem.c + dc[frontV];
    
                if (map[frontR][frontC] == 0) stack.push(new Elem(frontR, frontC, frontV, 1));
                else stack.push(new Elem(elem.r, elem.c, frontV, 0));
    
            } else {
    
                int backV = backTurn(elem.v);
    
                int backR = elem.r + dr[backV];
                int backC = elem.c + dc[backV];
                
                if (map[backR][backC] != 1) stack.push(new Elem(backR, backC, elem.v, 0));
            }        
        }
    }
    
    static int backTurn(int v) {
        int newV = (v + 2) % 4;
        return newV; 
    }

    static int leftTurn(int v)
    {
        int newV = (v + 3) % 4;
        return newV;
    }
}

 

 

3. BFS 구현

import java.io.*;
import java.util.*;

public class Main {
    
    static int N,M,R,C,V;
    static int[] dr = {-1,0,1,0};    
    static int[] dc = {0,1,0,-1};
    static int[][] map;
    static int cleanCnt;

    static class Elem {
        public int r,c,v,p;

        public Elem(int r, int c, int v, int p) {
            this.r = r;
            this.c = c;
            this.v = v;
            this.p = p;
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(stk.nextToken());        
        M = Integer.parseInt(stk.nextToken());

        map = new int[N][M];
        
        stk = new StringTokenizer(br.readLine(), " ");
        R = Integer.parseInt(stk.nextToken());        
        C = Integer.parseInt(stk.nextToken());
        V = Integer.parseInt(stk.nextToken());

        for (int i = 0; i < N; i++) {
            stk = new StringTokenizer(br.readLine(), " ");

            for (int j = 0; j < M; j++) map[i][j] = Integer.parseInt(stk.nextToken());
        }
        
        dfs(R,C,V,1);

        bw.write(cleanCnt + "");
        bw.flush();
        bw.close();
        br.close();
    }

    static void dfs(int r, int c, int v, int p) {
        
        Queue<Elem> queue = new ArrayDeque<>();
        queue.offer(new Elem(r,c,v,p));

        while(!queue.isEmpty()) {
            
            Elem elem = queue.peek();
            queue.poll();

            if (elem.p == 1) {
                map[elem.r][elem.c] = 2;
                cleanCnt++;
            }
    
            boolean flag = false;
    
            for (int i = 0; i < 4; i++) {
                int newR = elem.r + dr[i];
                int newC = elem.c + dc[i];
    
                if (map[newR][newC] == 0)
                {
                    flag = true;
                    break;
                }
            }
    
            if (flag) {
                int frontV = leftTurn(elem.v);
    
                int frontR = elem.r + dr[frontV];
                int frontC = elem.c + dc[frontV];
    
                if (map[frontR][frontC] == 0) queue.offer(new Elem(frontR, frontC, frontV, 1));
                else queue.offer(new Elem(elem.r, elem.c, frontV, 0));
    
            } else {
    
                int backV = backTurn(elem.v);
    
                int backR = elem.r + dr[backV];
                int backC = elem.c + dc[backV];
                
                if (map[backR][backC] != 1) queue.offer(new Elem(backR, backC, elem.v, 0));
            }        
        }
    }
    
    static int backTurn(int v) {
        int newV = (v + 2) % 4;
        return newV; 
    }

    static int leftTurn(int v)
    {
        int newV = (v + 3) % 4;
        return newV;
    }
}

 

 

 

Python

 

1. 재귀함수를 통한 DFS 구현

import sys
input = sys.stdin.readline

clear_cnt = 0
dr = [-1,0,1,0]
dc = [0,1,0,-1]

N, M = map(int,input().split())
r_map = [[0 for _ in range(M)] for _ in range(N)]
r,c,v = list(map(int, input().split()))

for i in range(0,N):
    input_list = list(map(int, input().split()))
    for j in range(0,M):
        r_map[i][j] = input_list[j]

def turn_left(v):
    left_v = (v + 3) % 4
    return left_v 
    
def turn_back(v):
    back_v = (v + 2) % 4
    return back_v 

def dfs(r, c, v, p):
    
    if (p == 1):
        global clear_cnt
        clear_cnt += 1
        r_map[r][c] = 2
    
    flag = False

    for i in range(0,4):
        next_r = r + dr[i]
        next_c = c + dc[i]

        if (r_map[next_r][next_c] == 0):
            flag = True
            break
    
    if (flag):
        front_v = turn_left(v)
        
        front_r = r + dr[front_v]
        front_c = c + dc[front_v]

        if (r_map[front_r][front_c] == 0):
            dfs(front_r, front_c, front_v, 1)
        else:
            dfs(r, c, front_v, 0)
        
    else:
        back_v = turn_back(v)
        
        back_r = r + dr[back_v]
        back_c = c + dc[back_v]

        if (r_map[back_r][back_c] != 1):
            dfs(back_r, back_c, v, 0)
    
    return


dfs(r,c,v,1)
print(clear_cnt)

 

2. Stack 을 사용한 DFS 구현

import sys
input = sys.stdin.readline

class Elem:
    def __init__(self, r, c, v, p):
        self.r = r
        self.c = c
        self.v = v
        self.p = p

clear_cnt = 0
dr = [-1,0,1,0]
dc = [0,1,0,-1]

N, M = map(int,input().split())
r_map = [[0 for _ in range(M)] for _ in range(N)]
r,c,v = list(map(int, input().split()))

for i in range(0,N):
    input_list = list(map(int, input().split()))
    for j in range(0,M):
        r_map[i][j] = input_list[j]

def turn_left(v):
    left_v = (v + 3) % 4
    return left_v 
    
def turn_back(v):
    back_v = (v + 2) % 4
    return back_v 

def dfs(r, c, v, p):

    stack = []
    stack.append(Elem(r, c, v, p))

    while stack:

        elem = stack.pop()

        if (elem.p == 1):
            global clear_cnt
            clear_cnt += 1
            r_map[elem.r][elem.c] = 2
        
        flag = False

        for i in range(0,4):
            next_r = elem.r + dr[i]
            next_c = elem.c + dc[i]

            if (r_map[next_r][next_c] == 0):
                flag = True
                break
        
        if (flag):
            front_v = turn_left(elem.v)
            
            front_r = elem.r + dr[front_v]
            front_c = elem.c + dc[front_v]

            if (r_map[front_r][front_c] == 0):
                stack.append(Elem(front_r, front_c, front_v, 1))
            else:
                stack.append(Elem(elem.r, elem.c, front_v, 0))
            
        else:
            back_v = turn_back(elem.v)
            
            back_r = elem.r + dr[back_v]
            back_c = elem.c + dc[back_v]

            if (r_map[back_r][back_c] != 1):
                stack.append(Elem(back_r, back_c, elem.v, 0))
    

dfs(r,c,v,1)
print(clear_cnt)

 

3. BFS 구현

import sys
from queue import Queue

input = sys.stdin.readline

class Elem:
    def __init__(self, r, c, v, p):
        self.r = r
        self.c = c
        self.v = v
        self.p = p

clear_cnt = 0
dr = [-1,0,1,0]
dc = [0,1,0,-1]

N, M = map(int,input().split())
r_map = [[0 for _ in range(M)] for _ in range(N)]
r,c,v = list(map(int, input().split()))

for i in range(0,N):
    input_list = list(map(int, input().split()))
    for j in range(0,M):
        r_map[i][j] = input_list[j]

def turn_left(v):
    left_v = (v + 3) % 4
    return left_v 
    
def turn_back(v):
    back_v = (v + 2) % 4
    return back_v 

def dfs(r, c, v, p):

    queue = Queue()
    queue.put(Elem(r, c, v, p))
    
    while not queue.empty():

        elem = queue.get()

        if (elem.p == 1):
            global clear_cnt
            clear_cnt += 1
            r_map[elem.r][elem.c] = 2
        
        flag = False

        for i in range(0,4):
            next_r = elem.r + dr[i]
            next_c = elem.c + dc[i]

            if (r_map[next_r][next_c] == 0):
                flag = True
                break
        
        if (flag):
            front_v = turn_left(elem.v)
            
            front_r = elem.r + dr[front_v]
            front_c = elem.c + dc[front_v]

            if (r_map[front_r][front_c] == 0):
                queue.put(Elem(front_r, front_c, front_v, 1))
            else:
                queue.put(Elem(elem.r, elem.c, front_v, 0))
            
        else:
            back_v = turn_back(elem.v)
            
            back_r = elem.r + dr[back_v]
            back_c = elem.c + dc[back_v]

            if (r_map[back_r][back_c] != 1):
                queue.put(Elem(back_r, back_c, elem.v, 0))
    

dfs(r,c,v,1)
print(clear_cnt)