Tag: 틀렸습니다 5

2021
0
ProgrammingBeakjoon

1194-달이차오른다_가자

백준 1194 - 달이 차오른다. 가자https://www.acmicpc.net/problem/1194 문제 해설기존 BFS문제를 푸는 형식에 비트마스킹까지 더해진 문제이다. 비트마스킹을 통해 키를 가지고 있는 각각의 상태들을 체크할 수 있다. 키는 총 6개가 주어지기 때문에 50x50x64 = 160,000 의 공간 복잡도를 갖게 돼 메모리 제한에 걸리지 않는다. 소스 코드#include <bits/stdc++.h>using namespace std;int N, M;char Map[55][55];bool check[1 << 6][55][55];int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};queue<pair<int, int>> q;int startY, startX;struct point { int y; int x; int key; int count;};int bfs() { queue<point> q; q.push({startY, startX, 0, 0}); check[0][startY][startX] = true; while (!q.empty()) { int cntY = q.front().y; int cntX = q.front().x; int cntKey = q.front().key; int cntCount = q.front().count; q.pop(); if (Map[cntY][cntX] == '1') { return cntCount; } for (int i = 0; i < 4; i++) { int ny = cntY + dy[i]; int nx = cntX + dx[i]; if (0 >= ny || ny > N || 0 >= nx || nx > M) { continue; } if (check[cntKey][ny][nx] == true) { continue; } if (Map[ny][nx] == '.') { check[cntKey][ny][nx] = true; q.push({ny, nx, cntKey, cntCount + 1}); } else { // 열쇠에 마주쳤을 경우 if ('a' <= Map[ny][nx] && Map[ny][nx] <= 'f') { int key = (1 << (Map[ny][nx] - 'a')); check[cntKey | key][ny][nx] = true; q.push({ny, nx, cntKey | key, cntCount + 1}); } // 문을 만났을 경우 if ('A' <= Map[ny][nx] && Map[ny][nx] <= 'F') { int door = (1 << (Map[ny][nx] - 'A')); if (door & cntKey) { check[cntKey][ny][nx] = true; q.push({ny, nx, cntKey, cntCount + 1}); } } // 출구를 만났을 경우 if (Map[ny][nx] == '1') { q.push({ny, nx, cntKey, cntCount + 1}); } } } } return -1;}void init() { for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { cin >> Map[i][j]; if (Map[i][j] == '0') { startY = i; startX = j; Map[i][j] = '.'; } } }}int main(void) { cin >> N >> M; init(); cout << bfs() << '\n'; return 0;}

0
ProgrammingBeakjoon

백준 3190 - 뱀

https://www.acmicpc.net/problem/3190 체점 현황 전체 소스 코드#include <bits/stdc++.h>using namespace std;int board[110][110];int board_size;int num_of_apple;int num_of_command;map<int, char> command;// 동, 남, 서, 북int dx[4] = {1, 0, -1, 0};int dy[4] = {0, 1, 0, -1};int direction[4] = {0, 1, 2, 3};struct snake { int y; int x; int dir;};int main(void) { cin >> board_size >> num_of_apple; for (int i = 0; i < num_of_apple; i++) { int y, x; cin >> y >> x; board[y][x] = 1; } cin >> num_of_command; for (int i = 0; i < num_of_command; i++) { int time; char dir; cin >> time >> dir; command[time] = dir; } queue<pair<int, int>> snake_tail; int snake_head_y = 1; int snake_haed_x = 1; int snake_dir = 0; snake_tail.push({1, 1}); board[1][1] = 2; int time = 0; while (true) { time++; snake_head_y += dy[snake_dir]; snake_haed_x += dx[snake_dir]; snake_tail.push({snake_head_y, snake_haed_x}); if (board[snake_head_y][snake_haed_x] == 2) { cout << time << '\n'; return 0; } if (0 >= snake_head_y || snake_head_y > board_size || 0 >= snake_haed_x || snake_haed_x > board_size) { cout << time << '\n'; return 0; } if (board[snake_head_y][snake_haed_x] == 1) { board[snake_head_y][snake_haed_x] = 2; } else { board[snake_head_y][snake_haed_x] = 2; board[snake_tail.front().first][snake_tail.front().second] = 0; snake_tail.pop(); } if (command.find(time) != command.end()) { char com = command[time]; command.erase(time); if (com == 'L') { snake_dir = (snake_dir + 3) % 4; } else { snake_dir = (snake_dir + 1) % 4; } } } return 0;}

2020
0
ProgrammingBeakjoon

백준 1600 - 말이 되고픈 원숭이

링크https://www.acmicpc.net/problem/1600 체점 현황 문제 풀이 말처럼 뛸 수 있는 횟수(k), width, height를 입력 받는다. field에 대한 정보를 입력 받는다. (0, 0)에서 시작해 (width-1, height-1)까지 갈 수 있는 최소 횟수를 탐색한다. 원숭이가 움직일 수 있는 방법은 두가지가 존재한다. 말처럼 뛸 수 있는 방법(k내의 횟수에서) 상하좌우로 움직일 수 있는 방법 말이 (width-1, height-1)에 도착하면 그 횟수를 반환한다. 만약 도착하지 못할 경우 -1을 반환한다. 말이 움직인 횟수를 출력해준다. 전체 소스 코드#include <bits/stdc++.h>using namespace std;int numOfKnight;int width, height;int field[202][202];bool check[31][202][202];int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};int horse_dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};int horse_dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};struct point { int k; int y; int x;};int bfs(int y, int x) { check[0][y][x] = true; queue<point> q; q.push({0, y, x}); int count = 0; while (!q.empty()) { int q_size = q.size(); while (q_size--) { int cntK = q.front().k; int cntY = q.front().y; int cntX = q.front().x; q.pop(); if (cntY == height - 1 && cntX == width - 1) { return count; } if (cntK < numOfKnight) { for (int i = 0; i < 8; i++) { int ny = cntY + horse_dy[i]; int nx = cntX + horse_dx[i]; if (0 > ny || ny >= height || 0 > nx || nx >= width) continue; if (field[ny][nx] == 0 && check[cntK + 1][ny][nx] == false) { check[cntK + 1][ny][nx] = true; q.push({cntK + 1, ny, nx}); } } } for (int i = 0; i < 4; i++) { int ny = cntY + dy[i]; int nx = cntX + dx[i]; if (0 > ny || ny >= height || 0 > nx || nx >= width) continue; if (field[ny][nx] == 0 && check[cntK][ny][nx] == false) { check[cntK][ny][nx] = true; q.push({cntK, ny, nx}); } } } count++; } return -1;}int main(void) { cin >> numOfKnight >> width >> height; for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { cin >> field[i][j]; } } int minValueOfMove = bfs(0, 0); cout << minValueOfMove << '\n'; return 0;}