[SWEA 1210] Ladder1

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh 

SW Expert Academy

#include <cstdio>
#include <cstring>
#include <vector>
int N;
int board[100 + 2][100 + 2];
int visited[100 + 2][100 + 2];

struct _st
{
	int x, y;
};

std::vector<_st> V;


void init()
{
	memset(board, 0, sizeof(board));
	memset(visited, 0, sizeof(visited));
	V.clear();
}

void input()
{
	scanf("%d", &N);
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			scanf("%d", &board[i][j]);
			if (i == 0 && board[i][j] == 1) V.push_back({ i, j });
		}
	}
}


bool is_end(int sx, int sy)
{
	// dir
	int dir_x[3] = { 0, 0, 1 };
	int dir_y[3] = { 1, -1, 0 };

	// init
	memset(visited, 0, sizeof(visited));
	int x = sx;
	int y = sy;
	visited[x][y] = 1;

	while (1) {
		if (x == 100 - 1) {
			if (board[x][y] == 2) return true;
			return false;
		}

		for (int p = 0; p < 3; p++) {
			int nx = x + dir_x[p];
			int ny = y + dir_y[p];

			if (nx < 0 || nx > 100 - 1 || ny < 0 || ny > 100 - 1) continue;
			if (board[nx][ny] == 0) continue;
			if (visited[nx][ny]) continue;
			x = nx;
			y = ny;
			visited[x][y] = 1;
			break;
		}
	}
}



int get_ladder()
{
	for (_st start : V) {
		//printf("=====================%d %d\n", start.x, start.y);
		if (is_end(start.x, start.y)) return start.y;
	}
}


int main()
{
	for (int t = 1; t <= 10; t++) {
		init();
		input();
		printf("#%d %d\n", t, get_ladder());
	}
	return 0;
}

사다리를 타고 내려가다가 좌 우에 길이 있으면 우선적으로 가야하므로 dir을 좌, 우 , 하 순으로 배치하였다. 

만약 board[][] == 1 이면 break하고 그 방향 우선적으로 갈 수 있도록 하였다. 

방문배열이 필요한 이유는 방향을 꺾을 때, 온 길을 되돌아가지 않기 위함이다.