2178
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
int N, M;
vector<vector<int>> maze;
vector<vector<int>> visited;
int dx[4] = {1, -1, 0, 0}; // 방향 벡터 (상하좌우)
int dy[4] = {0, 0, 1, -1};
int bfs(int startX, int startY) {
queue<pair<int, int>> q;
q.push({startX, startY});
visited[startX][startY] = 1;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
// 상하좌우로 이동
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 미로 범위를 벗어나지 않고, 방문하지 않은 1인 경우
if (nx >= 0 && ny >= 0 && nx < N && ny < M && maze[nx][ny] == 1 && visited[nx][ny] == 0) {
visited[nx][ny] = visited[x][y] + 1;
q.push({nx, ny});
}
}
}
return visited[N-1][M-1]; // 도착지점 (N, M)의 거리 반환
}
int main() {
cin >> N >> M;
maze.resize(N, vector<int>(M));
visited.resize(N, vector<int>(M, 0));
for (int i = 0; i < N; i++) {
string line;
cin >> line;
for (int j = 0; j < M; j++) {
maze[i][j] = line[j] - '0';
}
}
cout << bfs(0, 0) << endl;
return 0;
}
/*
코드 설명
입력 , 처리
maze는 미로를 저장하는 2차원 벡터이며, 각 요소는 0(이동 불가능) 또는 1(이동 가능)을 나타냅니다.
visited는 방문 여부와 현재 위치까지의 최단 거리를 저장하는 2차원 벡터임.
BFS 구현:
bfs 함수는 BFS를 이용해 최단 경로를 탐색함. 시작점 (0, 0)에서 큐에 넣고, 상하좌우 방향으로 이동 가능한 위치를 큐에 추가함.
visited[nx][ny]에 visited[x][y] + 1을 할당하여 시작점부터의 거리를 저장함.
최종적으로 (N-1, M-1) 위치의 값을 반환하여 최단 경로의 길이를 구함.
방향 벡터:
dx와 dy 배열은 상하좌우 이동을 위한 방향 벡터. 이를 통해 반복문을 사용하여 네 방향으로의 이동을 쉽게 처리할 수 있음.
*/
2331
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
// 다음 숫자를 계산하는 함수
int next_number(int num, int p) {
int total = 0;
while (num > 0) {
int digit = num % 10;
total += pow(digit, p);
num /= 10;
}
return total;
}
int main() {
int A, P;
cin >> A >> P;
unordered_map<int, int> visited; // 각 숫자의 순서를 저장
vector<int> sequence; // 수열 저장
int current = A;
int index = 0;
while (visited.find(current) == visited.end()) {
visited[current] = index;
sequence.push_back(current);
current = next_number(current, P);
index++;
}
// 반복이 시작되기 전의 수열의 길이
cout << visited[current] << endl;
return 0;
}
/*
입력 처리:
A와 P는 각각 수열의 시작 숫자와 각 자리 수를 P제곱하여 합을 구할 때 사용할 지수
next_number 함수:
주어진 숫자 num의 각 자리 숫자를 P제곱한 합을 계산하여 다음 숫자를 반환.
주요 로직:
visited는 각 숫자가 처음 등장한 순서를 저장하는 unordered_map. 이를 통해 수열에서 각 숫자의 인덱스를 추적할 수 있음.
sequence는 수열을 저장하는 벡터.
current는 현재 숫자를 나타내며, 시작 숫자인 A에서 시작하여 next_number 함수를 통해 다음 숫자로 계속 업데이트.
index는 현재 수열에서의 인덱스를 나타냄.
반복 탐색:
visited.find(current)가 visited의 끝에 도달할 때까지 수열을 탐색함. 즉, 현재 숫자가 이미 등장했다면 반복이 시작된 것.
반복이 시작되기 전에 등장한 숫자의 개수는 visited[current]에 저장된 값으로 구할 수 있음.
*/
개인 공부 UNITY Phton