[구현 알고리즘] 개임 개발 ★★☆

---

문제 설명 : 게임 캐릭터의 움직임을 테스트하려고 한다. 매뉴얼을 반복적으로 수행하면서 방문한 칸의 수를 출력하라

1. 현재 위치에서 왼쪽 방향으로 탐색한다
2. 왼쪽에 탐색하지 않은 칸이 존재하면 왼쪽으로 회전하고 앞으로 한 칸 전진한다
3. 현재 위치로부터 네 방향 모두 가본 칸이거나 바다로 되어있는 칸이라면 현재 방향을 유지한 채로 뒤로 한 칸 돌아간다. 만약 뒤쪽 방향이 바다라면 움직임을 멈춘다

입력 조건

• 조건 1 : 첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다 (3<=N,M<=50)
• 조건 2 : 둘째 줄에 캐릭터의 좌표 (A,B)와 바라보는 방향 d(0:북, 1:동, 2:남, 3:서)가 공백으로 구분하여 주어진다
• 조건 3 : 셋째 줄부터 맵이 주어진다 (0:육지, 1:바다)

출력 조건

• 조건 1 : 첫째 줄에 이동을 마친 캐릭터가 방문한 칸의 수를 출력한다

입력 예시

4 4
1 1 0
1 1 1 1
1 0 0 1
1 1 0 1
1 1 1 1

출력 예시

3

---

 

전형적인 시뮬레이션 문제이다. 코드 길이가 길어서 구현이 매우 피곤한 게 딱 삼성 공채 코딩테스트 유형이다

 

일반적으로 방향을 설정하여 이동하는 문제의 경우 dx,dy를 미리 만들어 방향을 정하는 것이 효과적이다

 

이렇게 소스 코드가 긴 경우 pseudo code를 미리 작성하는 것이 실수를 줄이는 방법이다

 

밑은 내가 임의로 작성한 pseudo code이다

/*

데이터 입력받기
while(true){
	for(현재 좌표의 주변 좌표들에 대해){
    	if(주변 좌표가 범위를 벗어날 경우) continue;
    	if(주변 좌표가 바다거나 이미 탐색한 경우) continue;
    	탐색 표시
    	현재 좌표 = 주변 좌표
    }
	if(좌표가 이동하지 않았을 경우){
    	if(뒤가 존재하는 경우){
        	if(뒤가 바다인 경우){
            	탐색한 타일갯수 출력
                return
            }
            else{	// 뒤가 육지인 경우
            	현재 좌표 = 뒤 좌표
            }
        }
        else{	// 뒤가 존재하지 않는 경우
        	탐색한 타일갯수 출력
            return
        }
    }
}	

*/

---

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int dx[4] = {-1,0,1.0};
int dy[4] = {0,1,0,-1};
int n, m;
int a, b;
int d;
int ans;
int board[51][51];
int check[51][51];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> a >> b >> d;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            cin >> board[i][j];
            if (board[i][j] == 1) check[i][j]=-1;
        }
    }
    check[a][b] = 1;
    pair<int, int> cur = { a,b };
    while (1) {
        int complete = 1;
        for (int i = d+3;i>=d;i--) {
            int dir = i % 4;
            int mx = cur.X + dx[dir];
            int my = cur.Y + dy[dir];
            if (mx < 0 || my < 0 || mx >= n || my >= m) continue;
            if (check[mx][my] != 0) continue;
            check[mx][my] = 1;
            d = dir;
            cur = {mx,my};
            complete = 0;
            break;
        }
        if (complete == 1) {
            int dir = (d + 2) % 4;
            if (cur.X + dx[dir] >= 0 && cur.Y + dy[dir] >= 0 && cur.X + dx[dir] < n && cur.Y + dy[dir] < m) {
                if (check[cur.X + dx[dir]][cur.Y + dy[dir]] == -1) {
                    for (int i = 0;i < n;i++) {
                        for (int j = 0;j < m;j++) {
                            if (check[i][j] == 1) ans++;
                            cout << check[i][j] << " ";
                        }
                        cout << '\n';
                    }
                    cout << ans;
                    return 0;
                }
                else {
                    cur = { cur.X + dx[dir],cur.Y + dy[dir] };
                }
            }
            else {
                for (int i = 0;i < n;i++) {
                    for (int j = 0;j < m;j++) {
                        if (check[i][j] == 1) ans++;
                        cout << check[i][j] << " ";
                    }
                    cout << '\n';
                }
                cout << ans;
                return 0;
            }
        }
    }
    return 0;
}

---