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)
Python
복사
제출 날짜
@3/18/2021
메모리
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);
}
C++
복사
