[스터디] 문제 풀이 - 5주차

실 - 1260, 2606, 1012, 11724, 3184, 16948
프 - 타겟 넘버

---

1260번

문제

dfs, bfs 기본 문제

파이썬 풀이

from collections import deque

def dfs(graph, start, visitied):
    visitied.append(start)
    print(start, end=' ')
    for i in graph[start]:
        if i not in visitied:
            dfs(graph, i, visitied)
            
def bfs(graph, start, visitied):
    q = deque([start])
    visitied.append(start)
    while q:
        n = q.popleft()
        print(n, end=' ')
        for i in graph[n]:
            if i not in visitied:
                q.append(i)
                visitied.append(i)
                
n, m, v = map(int, input().split())
graph = [[] for _ in range(n+1)]

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

for i, g in enumerate(graph):
    g.sort()
    graph[i] = g

dfs_visitied = []
bfs_visitied = []
dfs(graph, v, dfs_visitied)
print()
bfs(graph, v, bfs_visitied)

그래프 입력받고 정렬하는 부분을 빼먹어서 한 번 틀렸다.
문제를 잘 읽자..
visitied 부분을 빈 리스트로 만들고 not in 으로 판단하는 것 보다
[False] * (n+1) 만들고 T/F 판단하는게 더 빠르다!! (당연함)

그렇게 갑자기 시작된 속도를 향한 집착..

파이썬 풀이 - 2

from collections import deque

def dfs(graph, start, visitied):
    stack = [start]
    while stack:
        n = stack.pop()
        if not visitied[n]:
            print(n, end=' ')
            stack += sorted(graph[n], reverse=True)
            visitied[n] = True

def bfs(graph, start, visitied):
    q = deque([start])
    visitied[start] = True
    while q:
        n = q.popleft()
        print(n, end=' ')
        for i in sorted(graph[n]):
            if not visitied[i]:
                q.append(i)
                visitied[i] = True
                
n, m, v = map(int, input().split())
graph = [[] for _ in range(n+1)]

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

dfs_visitied = [False] * (n+1)
bfs_visitied = [False] * (n+1)
dfs(graph, v, dfs_visitied)
print()
bfs(graph, v, bfs_visitied)

DFS도 재귀를 사용하지 않고 구현하는 것이 더 빠르다.

C++ 풀이

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<vector<int>> graph;

void dfs(int v,  bool *visitied){
    vector<int> stack;
    stack.push_back(v);
    while(!stack.empty()){
        int n = stack.back();
        stack.pop_back();
        if(!visitied[n]){
            visitied[n] = true;
            printf("%d ", n);
            sort(graph[n].rbegin(), graph[n].rend());
            for(auto i: graph[n]){
                stack.push_back(i);
            }
        }
    }
}

void bfs(int v,  bool *visitied){
    queue<int> q;
    q.push(v);
    visitied[v] = true;
    while(!q.empty()){
        int n = q.front();
        q.pop();
        printf("%d ", n);
        sort(graph[n].begin(), graph[n].end());
        for(auto i: graph[n]){
            if(!visitied[i]){
                q.push(i);
                visitied[i] = true;
            }
        }
    }
}

int main(){
    int n, m, v;
    scanf("%d %d %d", &n, &m, &v);

    graph = vector<vector<int>>(n+1);
    bool dfs_visitied[n + 1], bfs_visitied[n + 1];

    fill(dfs_visitied, dfs_visitied + (n + 1), false);
    fill(bfs_visitied, bfs_visitied + (n + 1), false);

    for(int i = 0; i < m; ++i){
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    dfs(v, dfs_visitied);
    printf("\n");
    bfs(v, bfs_visitied);
}

이게 맞나..?
내가 썼지만 너무 길어서 읽기 싫어짐

2606번

문제

bfs 이용해 탐색할 때 +1

파이썬 풀이

import sys
from collections import deque

def bfs():
    q = deque([1])
    visitied[1] = True
    count = 0
    while q:
        n = q.popleft()
        for i in graph[n]:
            if not visitied[i]:
                q.append(i)
                visitied[i] = True
                count += 1
    return count
                
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

visitied = [False] * (n + 1)
print(bfs())

C++ 풀이

#include <iostream>
#include <queue>
#include <vector>

using namespace std;


int bfs(vector<int> graph[], bool *visitied){
    queue<int> q;
    q.push(1);
    visitied[1] = true;

    int count = 0;

    while(!q.empty()){
        int n = q.front();
        q.pop();
        for(auto i: graph[n]){
            if(!visitied[i]){
                q.push(i);
                visitied[i] = true;
                count++;
            }
        }
    }
    return count;
}


int main(){
    int c, v;
    scanf("%d\n%d", &c, &v);

    vector<int> graph[c + 1];
    bool visited[c + 1];
    fill(visited, visited + (c+1), false);

    for(int i = 0; i < v; ++i){
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);        
    }

    printf("%d", bfs(graph, visited));
}

1012번

문제

dfs를 이용해 한 묶음의 탐색이 끝날 때 마다 +1

파이썬 풀이

import sys
sys.setrecursionlimit(10**4)

def dfs(y, x):
    if x < 0 or x >= m or y < 0 or y >= n:
        return False
    if graph[y][x]:
        graph[y][x] = 0
        dfs(y-1, x)
        dfs(y, x-1)
        dfs(y+1, x)
        dfs(y, x+1)
        return True
    return False

t = int(input())

for _ in range(t):
    m, n, k = map(int, input().split())
    graph = [[0] * m for _ in range(n)]
    for _ in range(k):
        x, y = map(int, input().split())
        graph[y][x] = 1
        
    answer = 0
    for i in range(n):
        for j in range(m):
            if dfs(i, j):
                answer += 1

    print(answer)

C++ 풀이

#include <iostream>
#include <vector>

using namespace std;

int m, n, k;
vector<vector<bool>> graph;

bool dfs(int y, int x){
    if(x < 0 || y < 0 || x >= m || y >= n) return false;
    if(graph[y][x]){
        graph[y][x] = 0;
        dfs(y - 1, x);
        dfs(y, x - 1);
        dfs(y + 1, x);
        dfs(y, x + 1);
        return true;
    }
    return false;
}

int main(){
    int t;
    scanf("%d", &t);

    while(t){
        scanf("%d %d %d", &m, &n, &k);

        graph = vector<vector<bool>>(n, vector<bool>(m, 0));

        while(k){
            int x, y;
            scanf("%d %d", &x, &y);
            graph[y][x] = 1;
            --k;
        }

        int answer = 0;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                if(graph[i][j]){
                    dfs(i, j);
                    ++answer;
                }
            }
        }
        printf("%d\n", answer);
        --t;
    }
}

출력할 때 개행문자를 안넣어줘서 한 번 틀렸다,,

11724번

문제

주어진 노드를 모두 탐색하기 위해 bfs를 호출하는 횟수

파이썬 풀이

from collections import deque
import sys

input = sys.stdin.readline

def bfs(start):
    q = deque([start])
    while q:
        n = q.popleft()
        for i in graph[n]:
            if i in not_visitied:
                q.append(i)
                not_visitied.remove(i)
                
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    
not_visitied = deque([i for i in range(1, n+1)])
answer = 0

while len(not_visitied):
    i = not_visitied.popleft()
    bfs(i)
    answer += 1

print(answer)

시간 절약을 위한 별별 시도를 하였으나 계속 시간초과가 났던 문제
설마?! 하고 입력 방식을 바꿔주었더니 바로 통과함 ...

C++ 풀이

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> graph;
vector<bool> visitied;

void bfs(int start){
    int n;
    queue<int> q;
    q.push(start);
    visitied[start] = true;
    while(!q.empty()){
        n = q.front();
        q.pop();
        for(auto i: graph[n]){
            if(!visitied[i]){
                q.push(i);
                visitied[i] = true;
            }
        }
    }
}

int main(){
    int n, m, u, v, answer = 0;
    scanf("%d %d", &n, &m);

    graph = vector<vector<int>>(n+1);
    visitied = vector<bool>(n+1, false);

    while(m){
        scanf("%d %d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
        --m;
    }

    for(int i = 1; i < n+1; ++i){
        if(!visitied[i]){
            bfs(i);
            ++answer;
        }
    }
    printf("%d", answer);
}

3184번

문제

파이썬 풀이

C++ 풀이

16948번

문제

시작점부터 이동 가능한 방향에 대해 모두 체크 (bfs)

파이썬 풀이

from collections import deque
import sys

input = sys.stdin.readline

n = int(input())
r1, c1, r2, c2 = map(int, input().strip().split())
chessboard = [[0] * n for _ in range(n)]

# 이동 정의
dr = [-2, -2, 0, 0, 2, 2]
dc = [-1, 1, -2, 2, -1, 1]

def bfs(r1, c1, r2, c2):
    q = deque()
    q.append((r1, c1))  # 큐에 시작점 삽입
    while q:
        r, c = q.popleft()
        for i in range(6):
            # 이동 가능성 확인
            nr = r + dr[i]
            nc = c + dc[i]
            # 체스판 크기를 벗어나는 경우
            if nr < 0 or nc < 0 or nr >= n or nc >= n:  
                continue
            # 해당 노드를 처음 방문하는 경우
            if chessboard[nr][nc] == 0:  
                chessboard[nr][nc] = chessboard[r][c] + 1 # 경로 기록
                q.append((nr, nc))  # 탐색을 위해 큐에 추가
    answer = chessboard[r2][c2]
    if answer:
        return chessboard[r2][c2]
    else:
        return -1

print(bfs(r1, c1, r2, c2))

C++ 풀이

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> chessboard;
int n, r1, r2, c1, c2;

int bfs(int r1, int c1, int r2, int c2){
    int dr[] = {-2, -2, 0, 0, 2, 2};
    int dc[] = {-1, 1, -2, 2, -1, 1};
    int nr, nc, answer;
    queue<vector<int>> q;
    vector<int> temp = {r1, c1};
    q.push(temp);
    while(!q.empty()){
        int r, c;
        r = q.front()[0];
        c = q.front()[1];
        q.pop();
        for(int i = 0; i < 6; ++i){
            nr = r + dr[i];
            nc = c + dc[i];
            if(nr < 0 or nc < 0 or nr >= n or nc >= n){
                continue;
            } 
            if(!chessboard[nr][nc]){
                chessboard[nr][nc] = chessboard[r][c] + 1;
                temp = {nr, nc};
                q.push(temp);
            }              
        }
    }
    answer = chessboard[r2][c2];
    return answer > 0 ? answer : -1;
}

int main(){
    scanf("%d", &n);
    scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
    chessboard = vector<vector<int>>(n, vector<int>(n, 0));
    printf("%d\n", bfs(r1, c1, r2, c2));
}

---

타겟 넘버

문제

이진트리처럼 계산 결과를 같은 층에 저장

파이썬 풀이

from collections import deque

def solution(numbers, target):
    answer = 0
    q = deque([0])
    for i, n in enumerate(numbers):
        for _ in range(2**i):
            temp = q.popleft()
            q.append(temp + n)
            q.append(temp - n)
            
    answer = q.count(target)    
    return answer

C++ 풀이

#include <vector>
#include <queue>
#include <cmath>

using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    queue<int> q;
    q.push(0);
    
    for(int i = 0; i < numbers.size(); ++i){
        int n = numbers[i];
        for(int j = 0; j < int(pow(2, i)); ++j){
            int temp = q.front();
            q.pop();
            q.push(temp + n);
            q.push(temp - n);
        }
    }
    while(!q.empty()){
        int t = q.front();
        if(t == target) ++answer;
        q.pop();
    }
    
    return answer;
}