-
[백준][14503번] 로봇 청소기Algorithm/백준 2020. 4. 23. 22:57
https://www.acmicpc.net/problem/14503
14503번: 로봇 청소기
로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음
www.acmicpc.net
풀이과정
1. bfs를 이용하여 문제에 주어진 시퀀스를 이용했다.
소스코드
더보기#include<stdio.h> enum DIR {NORTH, EAST, SOUTH, WEST}; enum TYPE {EMPTY, WALL, CLEAR}; int map[50][50]; int dx[4] = { 0, 1, 0, -1 }; int dy[4] = { -1, 0, 1, 0 }; int N, M; struct robot { int x; int y; int d; }; robot r; int solution() { int answer = 0; while (1) { //현 위치 청소 if (map[r.y][r.x] == EMPTY) { map[r.y][r.x] = CLEAR; answer++; } int nextDir = r.d; int nx, ny; bool findNext = false; for (int i = 0; i < 4; i++) { nextDir--; if (nextDir < 0) { nextDir = WEST; } nx = r.x + dx[nextDir]; ny = r.y + dy[nextDir]; if (nx < 0 || ny < 0 || nx >= M || ny >= N || map[ny][nx] != EMPTY) continue; findNext = true; break; } if (findNext) { //찾음 r.x = nx; r.y = ny; r.d = nextDir; continue; } else { nx = r.x - dx[r.d]; ny = r.y - dy[r.d]; if (nx < 0 || ny < 0 || nx >= M || ny >= N || map[ny][nx] == WALL) { return answer; } else { r.x = nx; r.y = ny; } } } } int main() { scanf("%d %d", &N, &M); scanf("%d %d %d", &r.y, &r.x, &r.d); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { scanf("%d", &map[i][j]); } } printf("%d\n",solution()); }
결과
'Algorithm > 백준' 카테고리의 다른 글
[백준][14890번] 경사로 (0) 2020.04.25 [백준][14889번] 스타트와 링크 (0) 2020.04.23 [백준][14888번] 연산자 끼워넣기 (0) 2020.04.23 [백준][14501번] 퇴사 (0) 2020.04.22 [백준][14502번] 연구소 (0) 2020.04.22