[BOJ] ์ด๋ชจํ‹ฐ์ฝ˜(14226)

[๋ฐฑ์ค€(BOJ)] ์ด๋ชจํ‹ฐ์ฝ˜(14226) C++

๋ฌธ์ œ : BOJ_14226๋ฒˆ ์ด๋ชจํ‹ฐ์ฝ˜

๋ฌธ์ œ ์„ค๋ช…

bfs

์ฒ˜์Œ์— ํ•œ ๊ฐœ์˜ ์ด๋ชจํ‹ฐ์ฝ˜์ด ์žˆ๊ณ 
์ด๋ชจํ‹ฐ์ฝ˜์„ ํด๋ฆฝ๋ณด๋“œ์— ์ €์žฅํ•  ๋•Œ count +1
์ด๋ชจํ‹ฐ์ฝ˜์„ ๋ถ™์—ฌ๋„ฃ๊ธฐ ํ•  ๋•Œ count +1(ํด๋ฆฝ๋ณด๋“œ๊ฐ€ ๋น„์–ด์žˆ์œผ๋ฉด ์•ˆ ๋ฉ๋‹ˆ๋‹ค.)
ํ˜„์žฌ ์ด๋ชจํ‹ฐ์ฝ˜์˜ ์ˆ˜๋ฅผ -1 ํ•  ๋•Œ count +1
์ผ ๋•Œ ์ฃผ์–ด์ง€๋Š” ์ˆ˜์˜ ์ด๋ชจํ‹ฐ์ฝ˜ ๊ฐœ์ˆ˜๊ฐ€ ๋  ๋•Œ๊นŒ์ง€ ์ตœ์†Œ count๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.


Solution

์ตœ์†Ÿ๊ฐ’์„ ๊ตฌํ•ด์•ผ ๋˜๊ธฐ ๋•Œ๋ฌธ์— bfs๋ฅผ ์จ์•ผ ํ•˜๋Š”๋ฐ ์ข€ ๊นŒ๋‹ค๋กœ์šด ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
๋งค ํšŒ ์ˆ˜ ๋งˆ๋‹ค ์ด๋ชจํ‹ฐ์ฝ˜ ์ˆ˜ -1, ํด๋ฆฝ๋ณด๋“œ ๋ณต์‚ฌ, ํด๋ฆฝ๋ณด๋“œ ๋ถ™์—ฌ๋„ฃ๊ธฐ์˜ ์„ธ ๊ฐ€์ง€ ๊ฒฝ์šฐ์˜ ์ˆ˜๋กœ queue์— push ํ•ด์•ผ ๋˜์ง€๋งŒ,
ํ˜„์žฌ ์ด๋ชจํ‹ฐ์ฝ˜์˜ ์ˆ˜์™€ ํด๋ฆฝ๋ณด๋“œ์— ์ €์žฅ๋œ ์ด๋ชจํ‹ฐ์ฝ˜์˜ ์ˆ˜์— ๋”ฐ๋ผ ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ๋ชจ๋‘ ๋‹ฌ๋ผ์ง€๊ธฐ ๋•Œ๋ฌธ์—
vis[ํ˜„์žฌ ํ™”๋ฉด์˜ ์ด๋ชจํ‹ฐ์ฝ˜ ์ˆ˜][ํด๋ฆฝ๋ณด๋“œ์— ์ €์žฅ๋œ ์ด๋ชจํ‹ฐ์ฝ˜ ์ˆ˜]
๋กœ bfs๋ฅผ ํ•ด์ฃผ๋Š” ๊ฒŒ ์ด ๋ฌธ์ œ์˜ ์†”๋ฃจ์…˜์ž…๋‹ˆ๋‹ค!


Description

๋‘ ๊ฐœ์˜ pair๋ฅผ ์จ์„œ ์„ธ ๊ฐœ์˜ ๋ณ€์ˆ˜๋ฅผ queue์— ๋‹ด์Šต๋‹ˆ๋‹ค. (ํ˜„์žฌ ๊ฐ’, ํด๋ฆฝ๋ณด๋“œ ์ €์žฅ ๊ฐ’, ํšŸ์ˆ˜ ๊ฐ’)

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
int n,res;
int vis[1001][1001]; // vis[ํ˜„์žฌ ํ™”๋ฉด์˜ ์ด๋ชจํ‹ฐ์ฝ˜ ์ˆ˜][ํด๋ฆฝ๋ณด๋“œ์— ์ €์žฅ๋œ ์ด๋ชจํ‹ฐ์ฝ˜ ์ˆ˜]
queue < pair<int, pair<int, int>>> q; // ๋‘ ๊ฐœ์˜ pair๋ฅผ ์จ์„œ ์„ธ ๊ฐœ์˜ ๋ณ€์ˆ˜๋ฅผ queue์— ๋‹ด์•˜์Šต๋‹ˆ๋‹ค.
int main(void) {
	scanf("%d", &n);
	memset(vis, -1, sizeof(vis));
	vis[1][0] = 1;
	q.push({ 1,{0,0} });
	while (!q.empty()) {
		int now = q.front().first;
		int save = q.front().second.first;
		int cnt = q.front().second.second;
		if (now == n) {  // ์›ํ•˜๋Š” ์ˆ˜๋ฅผ queue์—์„œ ์ฐพ์œผ๋ฉด ๋ฐ”๋กœ break๋ฅผ ํ•ด ์ตœ์†Œ ํšŸ์ˆ˜ ๊ฐ’์„ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค.
			res = cnt;
			break;
		}
		q.pop();
		if (vis[now - 1][save] == -1) {
			if (now - 1 > 0) {
				vis[now - 1][save] = 1;
				q.push({ now - 1,{save,cnt + 1} });
			}
		}
		if (vis[now][now] == -1) {
			vis[now][now] = 1;
			q.push({ now,{now,cnt + 1} });
		}
		if (save != 0) {
			if (now+save<=1000) {
				if (vis[now + save][save] == -1) {
					vis[now + save][save] = 1;
					q.push({ now + save,{save,cnt + 1} });
				}
			}
		}
	}
	printf("%d\n", res);
	return 0;
}