문제

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

풀이

직관적인 알고리즘으로 푸는 문제가 있는 것이 아닌 정직한 구현 문제였다.

다른 bfs 문제와 비슷하게 동,서,남,북 4가지 방향을 탐색하여 해결하는 문제였다.

다만 조금 다른 부분은 4가지 방향이 모두 청소되어 있다면 현재 방향에서 한 칸 후진하는 기능이 추가되었다.

문제에서 알려준 방법대로 정확하게만 구현하면 통과되었다.

나는 3번 조건에서 탐색할 때 처음에 반시계 방향으로 90도 회전하여야 하는데 현재 위치부터 검사하고 90도 회전하는 식으로 순서를 바꿔 구현했더니 틀린 부분을 한참 찾지 못하였다.

이런 구현 문제 같은 경우 문제에 힌트가 나와있는 경우가 많으므로 주의 깊게 읽어보자.

코드

#include<bits/stdc++.h>
using namespace std;

int N, M;
int board[53][53];

int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int r, c, dir;
	cin >> N >> M;
	cin >> r >> c >> dir;
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> board[i][j];
		}
	}

	int cnt = 0;
	int curY = r + 1, curX = c + 1;
	
	while (1) {
		bool check = false;
		if (board[curY][curX] == 0) { //청소 안했다면 제자리 청소
			board[curY][curX] = 2;
			cnt++;
		}
		for (int i = 0; i < 4; i++) { //현재 방향부터 네 방향 탐색
			dir = (dir + 3) % 4;
			int nextY = curY + dy[dir];
			int nextX = curX + dx[dir];
			if (board[nextY][nextX] == 0) {
				curY = nextY;
				curX = nextX;
				check = true;
				break;
			}		
		}

		if (check) // 다음 청소할 구역이 있으면 바로 다음 칸으로 이동
			continue;

		if (board[curY - dy[dir]][curX - dx[dir]] != 1) {
			curY = curY - dy[dir];
			curX = curX - dx[dir];
		}
		else
			break;
	}

	cout << cnt;

	return 0;
}