14503: 로봇 청소기

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

14503번: 로봇 청소기

문제 설명

이 문제는 주어진 조건을 잘 구현하면 되는 전형적인 시뮬레이션 문제이다. 청소하는 영역의 개수를 구하는 문제.

핵심 아이디어

• 전형적인 시뮬레이션 문제
• 북 동 남 서 방향 정의 하기

# 북 동 남 서 방향 정의, x를 행(위,아래) y(좌,우)를 열로 생각하기
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

• 반시계 방향으로 90도 회전하는 함수 정의하기

def turn_left():
	global direction
    direction -= 1
    # 북: 0, 동: 1, 남: 2, 서: 3
    if direction == 3:
    	direction = 1

코드 구현

# 맵의 크기 입력받기
n,m = map(int, input().split())
# 로봇의 위치와 방향 입력받기
x,y,direction = map(int, input().split())
# 맵정보 입력받기
graph = []
for _ in range(n):
	graph.append(list(map(int, input().split())))

# 로봇 이동을 위한 방향 정의, 북 동 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 왼쪽으로 90도 회전하는 함수
def turn_left():
	global direction
	direction -= 1
	if direction == -1:
		direction = 3
# 로봇 방문 처리를 위한 리스트
visited = [[0] * m for _ in range(n)]
# 현재 위치 방문 처리 -> 청소했다는 뜻
visited[x][y] = 1
# 따라서 현재 위치는 청소했기 때문에 1부터 시작
ans = 1
# 회전횟수를 담는 변수
turn_time = 0
# 종료될때까지 반복
while True:
	# 1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸 청소
	# 위에서 처리 함
	# 2. 4방향 모두 청소 했다면
	if turn_time == 4:
		# 후진 가능하면 후진 안되면 멈춤
		nx = x - dx[direction]
		ny = y - dy[direction]
		if graph[nx][ny] == 0:
			x,y = nx, ny
		else:
			break
		# 1번으로 돌아가기 위해 회전횟수 초기화
		turn_time = 0
	# 3. 청소되지 않은 곳이 있다면
	turn_left()
	nx = x + dx[direction]
	ny = y + dy[direction]
	# 청소되지 않은 칸이 있다면 한 칸 전진
	if graph[nx][ny] == 0 and visited[nx][ny] == 0:
		visited[nx][ny] = 1
		# 한 칸 전진
		x,y = nx,ny
		# 청소 영역 +1
		ans += 1
		# 다음 반복문을 위해 회전횟수 초기화
		turn_time = 0
		continue
	else: # 왼쪽으로 회전했는데, 가본 칸이라면
		turn_time += 1

print(ans)

다른 로직

# 맵의 크기 입력받기
n, m = map(int, input().split())
# 로봇의 위치, 바라보는 방향 입력받기
x, y, direction = map(int, input().split())
# 맵 정보 입력받기
graph = []
for _ in range(n):
	graph.append(list(map(int, input().split())))
# 북 동 남 서 -> 0 1 2 3
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 로봇의 방문 여부를 위한 2차원 리스트 만들기
visited = [[0] * m for _ in range(n)]
# 로봇의 현재 위치를 청소 하자
visited[x][y] = 1
# 왼쪽 방향으로 90도 회전하는 함수 정의
def turn_left():
	global direction
	direction -= 1
	if direction == -1:
		direction = 3
# 청소 영여 카운트 변수
count = 1 # 현재를 청소했기 때문에 1부터 시작
# 4칸 기준으로 2,3번이 달라져서 회전 횟수 변수 필요
turn_time = 0 #
# 작동을 멈출 때 까지 반복한다
while True:
	# 1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸 청소
	# 위 에서 현재 칸 청소함
	# 2. 4방향 모두 청소한 경우
	if turn_time == 4:
		nx = x - dx[direction]
		ny = y - dy[direction]
		# 만약 후진 가능하다면 하기
		if graph[nx][ny] == 0:
			x, y = nx, ny # 후진 하기
		else:
			break
		# if 문 나와서 회전횟수 초기화
		turn_time = 0
	# 3. 청소되지 않은 방향이 있다면
	if turn_time != 4:
		turn_left() # 왼쪽으로 회전
		nx = x + dx[direction]
		ny = y + dy[direction]
		if graph[nx][ny] == 0 and visited[nx][ny] == 0:
			visited[nx][ny] = 1 # 방문해서 청소
			x, y = nx, ny
			# 청소 영역 증가
			count += 1
			# 다음 반복문을 위해 즉, 현재 위치에서 다시 반복
			# 하기 위해 회전횟수 초기화
			turn_time = 0
			continue
		else: # 회전했는데 이미 방문한적이 있다면
			turn_time += 1

print(count)

C++

#include <iostream>

using namespace std;

int n, m, x,y,direction;
int graph[50][50];
bool visited[50][50];

// 북 동 남 서
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };

// 왼쪽으로 90도 회전하는 함수 정의
void rotate_left() {
	direction -= 1;
	if (direction == -1) {
		direction = 3;
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	// 맵의 크기 입력받기
	cin >> n >> m;
	// 현재 좌표와 방향 입력 받기
	cin >> x >> y >> direction;
	// 1. 현재위치 방문처리
	visited[x][y] = true;

	// 전체 맵 정보 입력 받기
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int x;
			cin >> x;
			graph[i][j] = x;
		}
	}
	int cnt = 1;
	int turn_time = 0;
	// 시뮬레이션 시작
	while (true) {


		// 2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이
		// 없는 경우
		if (turn_time == 4) {
			int nx = x - dx[direction];
			int ny = y - dy[direction];
			// 뒤 쪽이 벽이라면
			if (graph[nx][ny] == 0) {
				// 후진 한다.
				x = nx;
				y =	ny;
			}
			else {
				break;
			}
			turn_time = 0; // 다음 탐색을 위해 초기화
		}
		// 3. 청소되지 않은 빈 칸이 있는 경우 
		// 3-1 회전한다.
		rotate_left();
		int nx = x + dx[direction];
		int ny = y + dy[direction];
		// 3-2 앞으로 갈 수 있으면 전진
		if (graph[nx][ny] == 0 && !visited[nx][ny]) {
			visited[nx][ny] = true;
			cnt += 1;
			x = nx;
			y = ny; // 전진
			// 다음 반복을 위해 초기화
			turn_time = 0;
			continue;
		}
		else {
			turn_time += 1;
		}

	}

	cout << cnt << '\n';

}