[BOJ] 백준 12851 숨바꼭질 2 / BFS

💭 문제 이해 수빈이는 동시에 -1, +1, *2 라는 세 가지의 선택지 중 하나를 골라 이동하게 된다. 이동하는 세 가지의 선택이 동시에 1초 씩 증가하므로 너비 우선 탐색을 선택했다. 가장 빠른 시간으로 찾아가는 방법이 총 몇 가지인지도 구해야 하는 것이 포인트이다. 현재 경로까지의 cnt가 다음 경로에도 합산이 되므로 마치 부분적으로 dp 문제와 같은 느낌이 들었다. 구현 언어: Python from collections import deque def solve(): global n, k, sec, cnt queue = deque() queue.append(n) # 시작점을 먼저 담는다. sec[n] = 0 cnt[n] = 1 while queue: now = queue.popleft() for n..

→2021.01.12

[BOJ] 백준 1697 숨바꼭질 / BFS

💭 문제 이해 수빈이는 동시에 -1, +1, *2 라는 세 가지의 선택지 중 하나를 골라 이동하게 된다. 이동하는 세 가지의 선택이 동시에 1초 씩 증가하므로 너비 우선 탐색을 선택했다. 주의해야할 점이 있었다. 1. (현재 위치, 거기까지 걸린 초) 를 튜플로 큐에 저장해서 사용 각 선택지가 이동하는 방법에 따라 시간이 다르므로, 이동하는 것에 따라 걸린 시간을 같이 보관했다. 2. 방문 체크가 필수이다. 방문했던 지점을 다시 밟는 것은 의미없는 것이다. 실컷 이동하다가 다시 같은 지점을 밟는 것은 결코 최소 거리가 될 수 없다. (+ 시간 초과 100%...) 구현 언어: Python from collections import deque from sys import stdin def solve(): ..

→2021.01.07

[BOJ] 백준 7569 토마토 / BFS

💭 문제 이해 역시 탐색문제로 BFS를 이용하여 풀어야 한다. 여섯 방향으로 동시에 진행하므로 너비 우선 탐색이 맞다고 판단하였다. 다른 문제와 차이점이라면 3차원 리스트를 이용하여야 한다는 점인데, arr[깊이][가로][세로] 인 것을 유의하여야 하는 문제이다. 구현 언어: Python import sys from collections import deque # 3차원 리스트는 arr[깊이][가로][세로]로 구성 # col, rol, height m, n, h = map(int, sys.stdin.readline().rstrip().split()) warehouse = [[list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)] ..

→2021.01.05

[BOJ] 백준 2644 촌수계산 / BFS, DFS

💭 풀이 과정 탐색 문제로서 BFS와 DFS 두 가지 방법 모두 가능한 문제이다. 입력으로 주어진 연결 관계를 2차원 리스트로 양 쪽 모두에 저장한다. visited 리스트에는 출발점에서 해당 번호의 노드까지 이동하는 거리(촌수)를 저장한다. visited의 도착점 위치 값이 0이면 가족 관계가 전혀 없다는 뜻이므로 -1을 출력하고, 값이 존재한다면 그 촌 수를 출력한다. 작성언어: Python BFS from sys import stdin from collections import deque n = int(stdin.readline().rstrip()) man1, man2 = map(int, stdin.readline().rstrip().split()) m = int(stdin.readline().rs..

→2021.01.05

[BOJ] 백준 2667 단지번호붙이기 / BFS, DFS

💭 풀이 과정 탐색 문제로서 BFS와 DFS 두 가지 방법 모두 가능한 문제이다. N의 크기가 최대 25로 매우 작다. 그러므로 n2의 방법으로 모든 공간을 탐색하며 집이 있는 공간인 1을 발견하면 그 지점에서 탐색을 시작한다. 탐색을 마치고 구해진 크기(단지 크기)를 리스트에 append한다. 모든 연산이 마치면 리스트에는 단지들의 크기가 저장된다. 리스트의 길이가 단지 수가 되고, 리스트를 오름차순 정렬하여 원소들을 출력하는 것으로 마친다. 작성언어: Python BFS from sys import stdin from collections import deque n = int(stdin.readline().rstrip()) square = [list(map(int, list(stdin.readline..

→2021.01.04

[BOJ] 백준 2887 행성 터널 / 최소 신장 트리(MST), 크루스칼

💣 문제 이해 x, y, z 좌표로 행성의 위치가 주어지고(노드), 그 행성들 사이의 거리가 가중치가 된다(간선). 행성과 행성 사이의 거리는 문제에 주어진 조건처럼 min(abs(x1-x2), abs(y1-y2), abs(z1-z2))가 된다. 이 문제는 크루스칼 알고리즘으로 풀이했다. 💭 풀이 과정 작성 언어: C++ #include #include #include #include using namespace std; class Planet { public: int x, y, z, index; Planet(int x, int y, int z, int index) { this->x = x; this->y = y; this->z = z; this->index = index; } }; class Tunne..

→2020.11.21

[프로그래머스] 가장 먼 노드 / 최단 경로, 다익스트라

💣 문제 이해 한 출발 정점에서 다른 모든 정점으로의 최단 경로 이동 비용을 계산하는 문제였다. 각 노드로 이동하는 최소 비용을 계산하여 그중 최대를 구한 후, 동일한 비용을 지불하는 경로의 수를 카운트 했다. 이 문제는 다익스트라 알고리즘으로 풀이했다. 💭 풀이 과정 작성 언어: C++ #include #include #include using namespace std; const int MAX = 20001; const int INF = 1e9; int dist[MAX] = {0, }; int solution(int n, vector edge) { int max_cost = 0; int result = 0; priority_queuepq; // 비용, 노드번호 vectornodes[n+1]; // 각..

→2020.11.21

[BOJ] 백준 1647 도시 분할 계획 / 최소 신장 트리(MST), 크루스칼

💣 문제 이해 최소 신장 트리를 구한 뒤, 마을을 두 개로 분할할 수 있도록 도로를 제거하여 총 유지비가 최소가 되도록 하면 된다. 이 문제는 크루스칼 알고리즘으로 풀이했다. 💭 풀이 과정 작성 언어: C++ #include #include #include using namespace std; class Road { public: int start, dest, weight; Road(int start, int dest, int weight) { this->start = start; this->dest = dest; this->weight = weight; } }; const int MAX = 1001; int home_cnt, road_cnt; vector roads; vector survived_lin..

→2020.11.20

[BOJ] 백준 1922 네트워크 연결 / 최소 신장 트리(MST), 크루스칼

💣 문제 이해 컴퓨터를 노드로, 선 연결을 간선으로 보고 주어진 그래프에서 최소 신장 트리(MST)의 합을 구하는 문제였다. 틀은 바뀌었지만 1197번 최소 스패닝 트리 와 그냥 동일하게 풀리는 문제이다. 크루스칼 알고리즘/프림 알고리즘 두 가지 방법으로 풀 수 있다. 이 문제는 크루스칼 알고리즘으로 풀이했다. 💭 풀이 과정 작성 언어: C++ #include #include #include using namespace std; class Line { public: int start, dest, weight; Line(int start, int dest, int weight) { this->start = start; this->dest = dest; this->weight = weight; } }; co..

→2020.11.19

[BOJ] 백준 14503 로봇 청소기 / 구현

💣 문제 이해 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 로봇 청소기는 다음과 같이 작동한다. 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. 네 방향 모두 ..

→2020.11.06