[2023 알고리즘 스터디] 5조 #4주차 - DFS & BFS 알고리즘

FOSCAR 알고리즘 스터디 4주차 5조 블로깅 - 이승찬

 

 

13913 숨바꼭질 4 - 코드 리뷰 박병규

• 알고리즘 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색
• 문제 링크

https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

 

• 풀이

BFS를 사용하여 풀었습니다

queue에 position과 cost값을 저장해두고 방문하지 않은 position에 대해 다음 풀이를 진행할 수 있도록 하였습니다.

x-1, x+1, x*2 각각의 3가지 방법으로 position의 값을 이동하였고 cost의 값을 +1을 진행해 주었습니다.

그리고 현재 위치가 k와 같을 때 풀이를 종료하였습니다.

그리고 arr배열에 이동 전의 위치 정보를 담아 둠을 통해서 방문했던 경로들을 출력 할 수 있도록 해주었습니다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <bitset>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <stack>


using namespace std;

int n, k, ans;
bool visited[100010]; // 방문 확인용
int arr[100010]; // 경로를 찾기위한 배열
queue<pair<int,int>> q; 
vector<int> path; // 경로 출력을 위한 vector


void solve(){
    q.push({n,0});
    visited[n] = true;
    arr[n] = -1;
    while(!q.empty()){
        int now_pos = q.front().first;
        int cost = q.front().second;
        q.pop();

        if(now_pos == k){
            ans = cost;
            break;
        }
        int x_1 = now_pos - 1;
        int x_2 = now_pos + 1;
        int x_3 = now_pos * 2;
        
        //x-1;
        if(x_1 >= 0 && !visited[x_1]){
            q.push({x_1,cost+1});
            visited[x_1] = true;
            arr[x_1] = now_pos;
        }
        //x+1;
        if(x_2 <= 100000 && !visited[x_2]){
            q.push({x_2,cost+1});
            visited[x_2] = true;
            arr[x_2] = now_pos;
        }
        //x*2
        if(x_3 <= 100000 && !visited[x_3]){
            q.push({x_3,cost+1});
            visited[x_3] = true;
            arr[x_3] = now_pos;
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> k;
    
    if (n == k) {
		cout << '0' << '\n' << n;
        return 0;
	}

    solve();
    
    cout << ans << '\n';
    path.push_back(k);
    
    int idx = k;
    while (arr[idx] != -1) {
        path.emplace_back(arr[idx]);
        idx = arr[idx];
    }
    
    for (int i = path.size() - 1; i >= 0; i--){
		cout << path[i] << ' ';
    }
	return 0; 
}

 

1963 소수 경로 - 코드 리뷰 이진호

• 알고리즘 분류 : 수학, 정수론, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 소수 판정, 에라토스테네스의 체
• 문제 링크

https://www.acmicpc.net/problem/1963

1963번: 소수 경로

 

• 풀이

import sys
from collections import deque
input = sys.stdin.readline

def getNumList(n):
    lis = [n // 1000, (n % 1000) // 100, (n % 100) // 10, n % 10]
    mem = lis[:]
    ret = []
    for i in range(1, 10):
        lis[0] = i
        ret.append(lis[0] * 1000 + lis[1] * 100 + lis[2] * 10 + lis[3])

    for j in range(1, 4):
        lis = mem[:]
        for i in range(0, 10):
            lis[j] = i
            ret.append(lis[0] * 1000 + lis[1] * 100 + lis[2] * 10 + lis[3])
    return ret

def solve(primes, a, b):
    visited = [False for _ in range(10000)]
    visited[a] = True
    que = deque()
    que.append((a, 0))
    while que:
        n, c = que.popleft()
        if n == b:
            print(c)
        for nn in getNumList(n):
            if visited[nn]:
                continue
            if primes[nn]:
                que.append((nn, c + 1))
                visited[nn] = True

if __name__ == '__main__':
    primes = [True for _ in range(10000)]
    primes[0], primes[1] = False, False
    for i in range(2, 10000):
        if primes[i] == False:
            continue
        else:
            for j in range(i*2, 10000, i):
                primes[j] = False
    for _ in range(int(input().rstrip())):
        a, b = map(int, input().rstrip().split())
        solve(primes, a, b)

1926 그림 - 코드 리뷰 이승찬

• 알고리즘 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
• 문제 링크

https://www.acmicpc.net/problem/1926

1926번: 그림

• 풀이

BFS를 사용하여 풀었습니다

이어진 부분을 확인한 후 그림의 넓이를 계속 확인하였습니다.

→ 입력 받은 graph에서 그림의 유무 확인

→ 확인하는 곳의 사방으로 확인

→→사방에 1로 존재하면 위 방식 반복

그림의 개수 count합니다.

from collections import deque

def bfs(graph, a, b):
    queue = deque()
    queue.append((a,b))
    graph[a][b] = 0
    cnt = 1

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                cnt += 1
                queue.append((nx,ny))
    return cnt

n,m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

paper = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            paper.append(bfs(graph, i ,j))

if len(paper) == 0:
    print(len(paper))
    print(0)
else:
    print(len(paper)) # 그림의 개수
    print(max(paper)) # 가장 넓은 그림의 넓이

1405 미친 로봇 - 코드 리뷰 박준석

• 알고리즘 분류 : 수학, 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 브루트포스 알고리즘, 백트래킹
• 문제 링크

https://www.acmicpc.net/problem/1405

1405번: 미친 로봇

• 풀이

로봇이 동서남북으로 N번 움직일 수 있다고 할 때, 이동 경로가 단순할 확률을 구하는 문제입니다.

N은 14보다 작거나 같은 자연수입니다.

그러므로 (14,14)에서 시작해 14칸을 움직여도 맵의 범위 내에 있을 수 있도록 29*29의 크기로 해야합니다. 맵의 가장 중앙지점부터 dfs를 실행합니다.

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

double p[4]; // 동서남북 확률
bool visited[29][29]; // 로봇이 방문한 적이 있는 위치인지 체크
int dx[4] = { 0, 0, 1, -1 }; // 동서남북 이동 거리
int dy[4] = { 1, -1, 0, 0 };
int N;
double ans;

void dfs(int x, int y, int depth, double probability) {
    if (visited[x][y]) { // 이미 방문한 위치인 경우
        return;
    }
    if (depth == n) { // n번의 행동을 다 한 경우
        ans += probability; // 단순한 경로이므로 확률 더하기
        return;
    }
    visited[x][y] = true; // 현재 위치를 방문 체크
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        dfs(nx, ny, depth + 1, probability * (p[i] / 100)); // 다음 위치로 이동
    }
    visited[x][y] = false; // 현재 위치를 다시 방문하지 않도록 체크 해제
}

int main() {
    cin >> N;
		for(int i = 0; i < N; i++){
			cin >> p[i];
		}
    //memset(visited, false, sizeof(visited)); // visited 배열 초기화
    ans = 0;
    dfs(14, 14, 0, 1); // 로봇의 초기 위치는 (14, 14)
    cout.precision(10); // 소수점 아래 10자리까지 출력
    cout << fixed << ans << endl;
    return 0;
}