로봇 청소기

Memo

언뜻 보면 BFS 문제 같지만, stpe이 나눠져 있고 자신의 방향에 따라서 조사해야하는 곳이나 움직여야 하는 곳이 다르다는 점에서 로봇의 상태에 따른 코드를 작성하면 되겠다 생각이 들었습니다.
재귀적으로 문제를 풀어낼 수 있었습니다.
return (5)를 해준 이유는 step_two의 return type이 int이기 때문에 어쩔수 없이 아무 값이나 리턴해 주었습니다. 더 좋은 방법이 있다면 dm 부탁드립니다.

Code

(+ 2021/04/07 파이썬 코드로 다시 풀어봤습니다)

import sys

N, M = map(int, input().split())
r, c, d = map(int, input().split())
dy = [-1, 0, 1, 0] #NESW
dx = [0, 1, 0, -1]
g_map = []
ans = 0
for i in range(N):
    g_map.append(list(map(int, sys.stdin.readline().split())))
visited = [[1 for _ in range(M)] for _ in range(N)]

def get_left_index(d):
    return (d + 3) % 4

def get_back_index(d):
    return (d + 2) % 4

def operation(depth):
    global r, c, d, N, M, ans
    if (visited[r][c]):
        visited[r][c] = 0 #1
        ans += 1
    if (depth == 4):
        back_index = get_back_index(d)
        r += dy[back_index]
        c += dx[back_index]
        if (r < 0 or r >= N or c < 0 or c >= M or g_map[r][c]):
            return (0)
        return (1)
    d = get_left_index(d)
    ny = r + dy[d]
    nx = c + dx[d]
    if (ny < 0 or ny >= N or nx < 0 or nx >= M or g_map[ny][nx] or not visited[ny][nx]):
        return(operation(depth + 1))
    r = ny
    c = nx
    return (1)

while (operation(0)):
    pass
print(ans)

제출 날짜

2021/03/18

메모리

2020 KB

시간

0 ms

#include <iostream>

int N, M;
bool visited[51][51];
bool g_map[51][51];

int r_i, r_j, r_d;
int ans;
int step_two(int cnt);

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> N >> M;
	std::cin >> r_i >> r_j >> r_d;
	for(int i = 0 ; i < N; i++)
		for(int j = 0 ; j < M ; j++)
			std::cin >> g_map[i][j];
	ans = 0;
}

void step_one()
{
	visited[r_i][r_j] = 1;
	ans++;
	step_two(0);
}

std::pair<int, int> step_two_left_direction(int i, int j)
{
	if (r_d == 0)//북
		return (std::make_pair(i, j - 1));
	else if (r_d == 1)//동
		return (std::make_pair(i - 1, j));
	else if (r_d == 2)//남
		return (std::make_pair(i, j + 1));
	else//서
		return (std::make_pair(i + 1, j)); 
}

std::pair<int, int> step_two_back(int i, int j)
{
	if (r_d == 0)//북
		return (std::make_pair(i + 1, j));
	else if (r_d == 1)//동
		return (std::make_pair(i, j - 1));
	else if (r_d == 2)//남
		return (std::make_pair(i - 1, j));
	else//서
		return (std::make_pair(i, j + 1)); 

}

void step_two_direction_left_change()
{
	if (r_d == 0)//북
		r_d = 3;
	else if (r_d == 1)//동
		r_d = 0;
	else if (r_d == 2)//남
		r_d = 1;
	else//서
		r_d = 2; 
}

int step_two(int cnt)
{
	std::pair<int, int>left = step_two_left_direction(r_i, r_j);
	int dy = left.first;
	int dx = left.second;
	if (dy < 0 || dy >= N || dx < 0 || dx >= M || g_map[dy][dx] || visited[dy][dx]) 
	{
		if (cnt == 4)
		{
			std::pair<int, int>back = step_two_back(r_i, r_j);
			dy = back.first;
			dx = back.second;
			if (dy < 0 || dy >= N || dx < 0 || dx >= M || g_map[dy][dx])
			{
				std::cout << ans;
				return (5);
			}
			r_i = dy;
			r_j = dx;
			step_two(0);
		}
		else
		{
			step_two_direction_left_change();
			step_two(cnt + 1);
		}
	}
	else
	{
		step_two_direction_left_change();
		r_i = dy;
		r_j = dx;
		step_one();
	}
	return (5);
}

void solve()
{
	step_one();
}

int main()
{
	input();
	solve();
	return (0);
}