swea 1210. [S/W 문제해결 기본] 2일차 - Ladder1

[문제]

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh&categoryId=AV14ABYKADACFAYh&categoryType=CODE

SW Expert Academy

[풀이]

bfs를 사용하여 풀었다. 왼쪽 오른쪽 아래 순서로 다음 칸이 0이 아닌지 확인하고 0이라면 현재 칸에서의 탐색을 마쳤다.

visited에 방문한 칸을 표시하여 왼쪽 또는 오른쪽으로 이동하다가 다시 반대방향으로 이동하는 것을 막았다.

왜 결과에 +1을 해야하는 지 잘 모르겠음..

 

#include <iostream>
#include <queue>
#include <cstring>//memset
using namespace std;

struct Pos {
	int x, y;
};

int Ladder[100][100];
bool visited[100][100];
const int dx[] = { 0,0,1 };//2:아래
const int dy[] = { -1,1,0 };//0:왼, 1:오

int bfs(int starty) {
	queue<Pos>q;
	memset(visited, false, sizeof(visited));
	q.push({ 0,starty });
	visited[0][starty] = true;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		if (Ladder[x][y] == 2) {
			return starty;
		}
		for (int i = 0; i < 3; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= 100 || ny < 0 || ny >= 100)
				continue;
			if (Ladder[nx][ny] != 0 && visited[nx][ny] == false) {
				visited[nx][ny] = true;
				q.push({ nx,ny });
				break;
			}
		}
	}
	return -1;
}

void solution() {
	int testcase;
	for (int t = 1; t <= 10; t++) {
		cin >> testcase;
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				cin >> Ladder[i][j];
			}
		}
		int res;
		for (int i = 0; i < 100; i++) {
			res = bfs(i);
			if (res != -1)
				break;
		}
		cout << '#' << testcase << ' ' << res + 1 << '\n';
	}
}

int main() {
	solution();
	return 0;
}