이 부분이다 이부분의 경우느 일단 우리가 방문할려는 지점이 방문되었는지 또한 우리가 방문할 발판이 100을 넘었는지를 검사한다. 넘으면 실행 하지 않는다 그후 사다리나 뱀이 있다면 그 발판을 밟지 않고 이어져있는 발판을 밟는다 그 후 이를 bfs에 넣는다. 만약 사다리나 뱀이없으면 해당 발판을 밟는다. 이게 풀이 로직이었다.
이 문제의 경우 쉬운 전형적인 bfs문제이다. 모든 정점을 시작점으로 bfs를 돌린다 그 후 정점을 시작점으로 돌리는 케이스마다의 각 정점의 layer의 합을 저장한 후 이를 비교하여 최솟값을 갖는 정점의 값을 출력해 주면 되는 문제였다
bfs의 기본적이 풀이 로직은 이 블로그의 다른글들에 있다. 코드는 아래와 같다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, M;
vector<int> bfsv[101];
int arr[101] = { 0, };
int main() {
queue<pair<int, int>> bfsq;
cin >> N >> M;
for (int i = 0; i < M; i++) {
int temp1, temp2;
cin >> temp1 >> temp2;
bfsv[temp1].push_back(temp2);
bfsv[temp2].push_back(temp1);
}
for (int i = 1; i <= N; i++) {
int start = i;
bfsq.push({ start,0 });
bool isVisited[101] = { 0, };
while (!bfsq.empty()) {
int front = bfsq.front().first;
int second = bfsq.front().second;
arr[front] += second;
isVisited[front] = true;
bfsq.pop();
for (int j = 0; j < bfsv[front].size(); j++) {
if (!isVisited[bfsv[front][j]]) {
bfsq.push({ bfsv[front][j], second + 1 });
isVisited[bfsv[front][j]] = true;
}
}
}
}
int min=5001;
int ans = 0;
for (int i = 1; i <= N; i++) {
if (min > arr[i]) {
ans = i;
min = arr[i];
}
}
cout << ans;
}
일단 위 코드의 이부분은 pair로 이루어진 큐에서 값을 뽑고 그값을 기준으로 상하좌우의 값을 큐에다가 다시 넣어준다 그후 넣어준큐의 순서에대한 값이 저장되어있는 answer배열에 나의 방문번째수 +1을 넣어서 해준다 즉 내가 2번 layer에 자식이라면 나의 상하좌우는 3번 layer 에 자식이된다
트리로 그리게 되면 이런 구조가 된다. 그후 내가 몇번째 layer에 있는지를 answer배열에 저장해주면 된다.
이러한 문제류는 이제 dfs든 bfs로 풀기 쉬워졌다 이문제의 경우 자신을 기준으로 상하좌우로만 이동 할 수있기때문에 깊이우선 탐색으로 풀어 보았다 이문제는 어차피 단지의 개수를 세야 하기때문에 모든점을 한번에 다방문하면서 개수를 셀수 있는 dfs를 사용하였다. 이문제의 핵심 부분은
이문제는 요즘 나의 경악스러운 알고리즘 실력에 실망하던차에 내가 빠르게 풀 수 있는 문제였다. 아직 고수가 되긴 멀었지만 빨리 이런 문제쯤은 10분만에 해치울 수 있는 파워 프로그래머가 되고 싶다!!!!!
이 문제의 경우 여러방식으로 풀 수 있다. 나의 경우 일반적으로 성능이 나쁘지 않은 BFS를 사용해서 풀었다
자 이문제를 풀때는 처음 1인애를 만나면 루프를 돌면서 자신을 기준으로 갈 수 있는 모든 점들을 BFS로 접근하여 visited배열에 마킹합니다 visited 배열이 1로 마킹되면 다시 해당하는 곳을 접근 하지 않습니다 이렇게 빨간색으로 체크 된 1을 root로 나머지 1로마킹된 애들이 BFS 로서 빨갛게 1로 마킹된 애들부터 같은색깔안에 있는 영역으로 접근합니다.
#include <iostream>
#include <queue>
using namespace std;
bool cabbage[52][52];
int visited[52][52];
int main() {
int T; //테스트 케이스의 개수
int M, N, K;//M:가로길이 N:세로길이 K: 배추가 심어져있는 위치의 개수;'
cin >> T;
queue<pair<int, int>> bfsQueue;
for (int i = 0; i < T; i++) {
cin >> M >> N >> K;
for (int j = 0; j < M; j++) {
for (int k = 0; k < N; k++) {
cabbage[j][k] = 0;
visited[j][k] = 0;
}
}
for (int j = 0; j < K; j++) {
int temp1, temp2;
cin >> temp1 >> temp2;
cabbage[temp1][temp2] = 1;
}
int countnum = 0;
for (int j = 0; j < M; j++) {
for (int k = 0; k < N; k++) {
if (visited[j][k] == 1 && cabbage[j][k]==1)
continue;
else if(visited[j][k]==0 && cabbage[j][k]==1){
countnum += 1;
cabbage[j][k] = 1;
bfsQueue.push(pair<int, int>(j, k));
while (!bfsQueue.empty()) {
int firstn,secondn;
firstn = bfsQueue.front().first;
secondn = bfsQueue.front().second;
bfsQueue.pop();
if (firstn >= 1) {
if (visited[firstn - 1][secondn]==0 &&cabbage[firstn-1][secondn] == 1) {
bfsQueue.push(pair<int, int>(firstn - 1, secondn));
visited[firstn - 1][secondn] = 1;
}
}
if (secondn >= 1) {
if (visited[firstn][secondn - 1] == 0 && cabbage[firstn][secondn - 1]==1) {
bfsQueue.push(pair<int, int>(firstn, secondn - 1));
visited[firstn][secondn - 1] = 1;
}
}
if (visited[firstn + 1][secondn] == 0 && cabbage[firstn + 1][secondn]==1) {
bfsQueue.push(pair<int, int>(firstn + 1, secondn));
visited[firstn + 1][secondn] = 1;
}
if (visited[firstn ][secondn+1] == 0 && cabbage[firstn][secondn + 1]==1) {
bfsQueue.push(pair<int, int>(firstn , secondn+1));
visited[firstn][secondn + 1] = 1;
}
}
}
}
}
cout << countnum << '\n';
}
}
for (int j = 0; j < M; j++) {
for (int k = 0; k < N; k++) {
cabbage[j][k] = 0;
visited[j][k] = 0;
}
}
for (int j = 0; j < K; j++) {
int temp1, temp2;
cin >> temp1 >> temp2;
cabbage[temp1][temp2] = 1;
}
일단 이부분은 각 케이스의 접근할때 배열들을 초기화 한후 양배추가 위치한곳을 1로 체크해줍니다
