[softeer/C++] [인증평가(1차) 기출] 로봇이 지나간 경로

[인증평가(1차) 기출] 로봇이 지나간 경로

DFS

#include<iostream>
#include<string>

using namespace std;

int H, W;
int map[26][26];
int visited[26][26];
int dy[] = { 1,0,-1,0 };
int dx[] = { 0,-1,0,1 };
int a, b;

string dir = ">^<v";
int d;
void func1() {
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			int num = 0;
			for (int k = 0; k < 4; k++) {
				int nx = i + dx[k];
				int ny = j + dy[k];
				if (nx >= 0 && ny >= 0 && nx < H && ny < W) {
					if (map[i][j] && map[nx][ny]) {
						num++;
					}
				}
			}
			if (num == 1) {
				a = i;
				b = j;
				for (int k = 0; k < 4; k++) {
					int nx = i + dx[k];
					int ny = j + dy[k];
					if (nx >= 0 && ny >= 0 && nx < H && ny < W) {
						if (map[i][j] && map[nx][ny]) {
							d = k;
						}
					}
				}
				return;
			}
		}
	}
}

void func2(int x, int y) {
	visited[x][y] = 1;
	x += dx[d];
	y += dy[d];
	cout << "A";
	visited[x][y] = 1;

	for (int k = 0; k < 4; k++) {
		int nx = x + dx[k];
		int ny = y + dy[k];
		if (nx >= 0 && ny >= 0 && nx < H && ny < W) {
			if (map[nx][ny] && visited[nx][ny] == 0) {
				int move = d - k;
				if (move == -1 || move == 3) {
					cout << "L";
				}
				else if (move == 1 || move == -3) {
					cout << "R";
				}
				d = k;
				func2(nx, ny);
			}
		}
	}
}

int main(int argc, char** argv)
{

	cin >> H >> W;
	string input;
	for (int i = 0; i < H; i++) {
		cin >> input;
		for (int j = 0; j < W; j++) {
			if (input[j] == '#') {
				map[i][j] = 1;
			}
			else if (input[j] == '.') {
				map[i][j] = 0;
			}
		}
		cout << "\n";
	}

	func1();
	cout << a + 1 << " " << b + 1 << "\n";
	cout << dir[d] << "\n";
	visited[a][b] = 1;
	func2(a + dx[d], b + dy[d]);
	return 0;
}