[BOJ] ํด์งํด์ง(1326)

[๋ฐฑ์ค€(BOJ)] ํด์งํด์ง(1326) C++

๋ฌธ์ œ : BOJ_1326๋ฒˆ ํด์งํด์ง

๋ฌธ์ œ ์„ค๋ช…

bfs, pair

bfs๋ฅผ ์ด์šฉํ•œ ์ตœ์†Œ ์ ํ”„ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
์œ ์‚ฌํ•œ ๋ฌธ์ œ๋กœ๋Š” bfs๋ฅผ ํ™œ์šฉํ•œ ๋ฐฑ์ค€ 1697๋ฒˆ ์ˆจ๋ฐ”๊ผญ์งˆ์ด ์žˆ์Šต๋‹ˆ๋‹ค.


Solution

dfs์™€ bfs๋ฅผ ์ด์šฉํ•˜๋Š” ๋ฌธ์ œ๋“ค ์ค‘ ์–ด๋–ค ์ƒํ™ฉ์—์„œ ๋‘ ๊ฐœ ์ค‘ ํ•˜๋‚˜๋ฅผ ์„ ํƒํ•ด์•ผ ๋˜๋Š”์ง€ ๊ณ ๋ฏผ์ด ๋  ๋•Œ๊ฐ€ ์žˆ๋Š”๋ฐ,
๋ชฉ์ ์ง€์— ๋„๋‹ฌํ•˜๋Š” ์—ฌ๋Ÿฌ ๊ฐ€์ง€ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๋‹ค ํ™•์ธํ•ด์•ผ ๋˜๊ธฐ๋ณด๋‹ค๋Š” ๋ชฉ์ ์ง€์— ๋„๋‹ฌํ•˜๋Š” ์ตœ์†Œ ๊ฑฐ๋ฆฌ, ์ตœ์†Œ ์‹œ๊ฐ„ ๋“ฑ์˜ ๋ฌธ์ œ๋ฅผ ํ’€ ๋•Œ๋Š” ๋ณดํ†ต bfs๋กœ ํ’€๋ฆฌ๋Š” ๋ฌธ์ œ๋“ค์ด ๋งŽ์Šต๋‹ˆ๋‹ค.


Description

  1. ์ง•๊ฒ€๋‹ค๋ฆฌ์— ์“ฐ์—ฌ ์žˆ๋Š” ์ˆ˜ ๋“ค์„ ๊ฐ ์ง•๊ฒ€๋‹ค๋ฆฌ์˜ ๋ฒˆํ˜ธ์— ๋งž๋Š” ๋ฐฐ์—ด์— ๋„ฃ์–ด์ค€๋‹ค.
  2. pair๋ฅผ ์ด์šฉํ•˜์—ฌ ๋„๋‹ฌํ•œ ์ง•๊ฒ€๋‹ค๋ฆฌ์˜ ๋ฒˆํ˜ธ๋ฅผ pair์˜ first์—, ๋„๋‹ฌํ•˜๊ธฐ๊นŒ์ง€ ์ ํ”„ํ•œ ํšŸ์ˆ˜๋ฅผ pair์˜ second์— push
#include <iostream>
#include <queue>
using namespace std;
queue<pair<int, int>>q;
int st, ed, jump[10001], roof, vis[10001], swc, res; /*swc == switch ์›ํ•˜๋Š” ์ง•๊ฒ€๋‹ค๋ฆฌ์—
๋„๋‹ฌํ•˜์ง€ ๋ชปํ•œ๋‹ค๋ฉด, swc == 0 ์ด ๋˜๊ฒŒํ•˜์—ฌ -1์„ ์ถœ๋ ฅํ•˜๊ธฐ ์œ„ํ•œ ๋ณ€์ˆ˜์ž…๋‹ˆ๋‹ค. */
int main() {
	cin >> roof;
	for (int i = 1; i <= roof; i++) {
		cin >> jump[i]; // ์ง•๊ฒ€๋‹ค๋ฆฌ์— ๋ฒˆํ˜ธ์— ์“ฐ์—ฌ์žˆ๋Š” ์ˆ˜๋ฅผ ๋„ฃ์–ด์ค๋‹ˆ๋‹ค.
	}
	cin >> st;
	cin >> ed;
	q.push(make_pair(st, 0)); // st==์‹œ์ž‘ ์ง•๊ฒ€๋‹ค๋ฆฌ, 0==์ ํ”„ํ•œ ํšŸ์ˆ˜
	vis[st] = 1;
	while (!q.empty()) {
		if (q.front().first == ed) {
			res = q.front().second;
			swc++; // q.front().first๊ฐ€ ๋ชฉํ‘œํ•œ ์ง•๊ฒ€๋‹ค๋ฆฌ์— ๋„๋‹ฌํ–ˆ์„ ๋•Œ swc==1์ด ๋ฉ๋‹ˆ๋‹ค.
			break;
		}
		int now = q.front().first; // now==ํ˜„์žฌ์œ„์น˜
		int cnt = q.front().second; // cnt==count ์ ํ”„ํ•œ ํšŸ์ˆ˜
		q.pop();
		for (int i = 1; now + (jump[now] * i) <= roof; i++) {
			int next = now + jump[now] * i;
			if (vis[next] == 0) {
				vis[next] = 1;
				q.push(make_pair(next, cnt + 1));
			}
		}
		for (int i = 1; now - (jump[now] * i) >= 1; i++) {
			int next = now - jump[now] * i;
			if (vis[next] == 0) {
				vis[next] = 1;
				q.push(make_pair(next, cnt + 1));
			}
		}
	}
	if (swc == 0) {
		cout << -1;
	}
	else cout << res; //swc==1์ด๋ผ๋ฉด ๋„๋‹ฌํ•˜๊ธฐ๊นŒ์ง€ ์ ํ”„ํ•œ ํšŸ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค.
}