[2020 카카오 공채] 블록 이동하기

블록 이동하기

 

---

Problem?

문제 링크 : [2020 카카오 공채] 블록 이동하기

 

 

Solution

bfs문제

bfs()를 통해 가능 경로를 탐색한다

핵심적인 내용은 아래의 그림을 보면서 참고

 

 

가정 isSafeTurn : 회전가능 여부확인 solution() : 문제 해결 코드   struct robot : queue에 넣을 구조체 turnDir : 회전하는 경우 이동 경로 safeTurn : 안전한 회전 여부 확인을 위한 위치 goDir : 회전하지 않는 경우 이동 경로 visited : 방문 여부 확인 <y, x, dir> N : 배열의 사이즈

Code(핵심 코드)

int bfs(vector<vector<int>> board, int y, int x) {
	queue<robot> q;			// queue
	robot t(0, 0, 1, 0);
	q.push(t);
	visited[0][0][1] = true;

	while (!q.empty()) {
		int curY = q.front().y;		int curX = q.front().x;
		int curDir = q.front().dir;	int curCnt = q.front().cnt;
		q.pop();

		// end state
		if (curDir) {	// 가로
			if (curY == N - 1 && (curX + 1) == N - 1)
				return curCnt;
		}
		else {			// 세로
			if ((curY + 1) == N - 1 && curX == N - 1)
				return curCnt;
		}

		// turn case (회전)
		for (int i = 0; i < 4; i++) {
			if (curDir == 1) {	// 가로 -> 세로
				int nextY = curY + turnDir[i].first;
				int nextX = curX + turnDir[i].second;
				int nextDir = (curDir == 0) ? 1 : 0;

				if (0 <= nextY && nextY < N - 1 && 0 <= nextX && nextX < N)
					if (!board[nextY][nextX] && !board[nextY + 1][nextX] && !visited[nextY][nextX][nextDir])
						if (isSafeTurn(board, nextY, nextX, curDir, i)) {
							robot tmp(nextY, nextX, nextDir, curCnt + 1);
							q.push(tmp);
							visited[nextY][nextX][nextDir] = true;
						}
			}
			else {				// 세로 -> 가로
				int nextY = curY + turnDir[i].second;
				int nextX = curX + turnDir[i].first;
				int nextDir = (curDir == 0) ? 1 : 0;

				if (0 <= nextY && nextY < N && 0 <= nextX && nextX < N - 1)
					if (!board[nextY][nextX] && !board[nextY][nextX + 1] && !visited[nextY][nextX][nextDir])
						if (isSafeTurn(board, nextY, nextX, curDir, i)) {
							robot tmp(nextY, nextX, nextDir, curCnt + 1);
							q.push(tmp);
							visited[nextY][nextX][nextDir] = true;
						}
			}
		}

		// go back case (앞뒤로 왔다갔다하는 경우)
		for (int i = 0; i < 4; i++) {
			if (curDir) {		// 가로 -> 가로
				int nextY = curY + goDir[i].first;
				int nextX = curX + goDir[i].second;

				if (0 <= nextY && nextY < N && 0 <= nextX && nextX < N - 1) {
					if (!board[nextY][nextX] && !board[nextY][nextX + 1] && !visited[nextY][nextX][curDir]) {
						robot tmp(nextY, nextX, curDir, curCnt + 1);
						q.push(tmp);
						visited[nextY][nextX][curDir] = true;
					}
				}
			}
			else {				// 세로 -> 세로
				int nextY = curY + goDir[i].first;
				int nextX = curX + goDir[i].second;

				if (0 <= nextY && nextY < N - 1 && 0 <= nextX && nextX < N) {
					if (!board[nextY][nextX] && !board[nextY + 1][nextX] && !visited[nextY][nextX][curDir]) {
						robot tmp(nextY, nextX, curDir, curCnt + 1);
						q.push(tmp);
						visited[nextY][nextX][curDir] = true;
					}
				}
			}
		}
	}
	return -1;	// error code
}

 

---

bfs()문제

 

* 문제 있을 시 삭제하겠습니다.