Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- 프로그램
- 개인프로젝트
- backend
- frontend
- 프로그래밍
- Reflex
- C++
- 프로그래머스
- 풀스택프레임워크
- 개발자
- 사물인터넷
- SNS
- 코테
- 이웃한 칸
- 코딩독학
- java
- 백준
- 코딩
- 자바정리
- 코스닥
- 자바
- 개발
- Python
- java정리
- Project
- 코딩테스트
- 빅데이터
- 자바독학
- 주가예측
- 모의 주식
Archives
- Today
- Total
Creative Code
[16928번]뱀과 사다리 게임 본문
https://www.acmicpc.net/problem/16928
16928번: 뱀과 사다리 게임
첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으
www.acmicpc.net
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
int dx[] = { 1,2,3,4,5,6 }; // 주사위를 던졌을 때 나오는 눈금의 종류
bool visit[101];
int main() {
cout.tie(0);
cin.tie(0);
ios_base::sync_with_stdio(false);
int N,M; // 사다리의 수 N, 뱀의 수 M
cin >> N >> M;
map<int,int>ladder; // 사다리의 정보를 저장할 map
map<int,int>snake; // 뱀의 정보를 저장할 map
for (int i = 0; i < N; i++) {
int a, b;
cin >> a >> b; //사다리 시작점,끝점
ladder[a] = b;
}
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b; //뱀 시작점, 끝점
snake[a] = b;
}
queue<pair<int, int>>q; // 현재위치와 해당위치까지 오는데 던진 주사위의 수
q.push(make_pair(1, 0)); // 초기 위치는 1번칸, 주사위 던진횟수 0
visit[1] = true; // 방문 체크
while (!q.empty()) { //bfs문
int x = q.front().first;
int y = q.front().second;
visit[x] = true;
q.pop();
for (int i = 0; i < 6; i++) {
int nx = x + dx[i];
int ny = y + 1;
if (visit[nx] == true) { //이미 방문한 칸이면 건너 뜀
continue;
}
if (nx >= 100) {
printf("%d", ny); // 가장먼저 100번째 칸에 도착하면 result벡터에 횟수를 넣고 멈춤
return 0;
}
else {
if (ladder.find(nx) != ladder.end()) { // 주사위를 던져 도착한 칸이 사다리일 경우
q.push(make_pair(ladder[nx], ny));
}
else if (snake.find(nx) != snake.end()) { // 주사위를 던져 도착한 칸이 snake일 경우
q.push(make_pair(snake[nx], ny));
}
else {
q.push(make_pair(nx, ny)); // 도착한 칸에 사다리와 뱀이 아무것도 없을 때
}
}
}
}
}
'백준 문제풀이' 카테고리의 다른 글
[1753번]최단경로 (0) | 2023.09.24 |
---|---|
[1043번]거짓말 (0) | 2023.09.24 |
[12856번]평범한 배낭 (0) | 2023.09.24 |
[10026번]적록색약 (0) | 2023.09.24 |
[7576번]토마토 (0) | 2023.09.24 |