Smallsoft

문제링크문제요약3차원의 토마토박스가 주어지고 탐색을하는 문제이다. 익은 토마토는 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 총 여섯 방향의 토마토에 영향을 미친다. 이때 토마토가 다 익는 최소날짜를 구하는 문제이다.어떻게 풀어야 할까문제 자체는 배열을 탐색해서 최소일수를 구하는 bfs 문제이다. 다만 3차원이기 때문에 방향이 2차원일때와 다르게 두곳을 더 갈 수 있다. 조금 귀찮지만 2차원 bfs를 잘했다면 못할 문제도 아니다. 다른 문제점은 시작지점이 여러군대 일 수 있는건데, 그냥 이 모든 시작점을 큐에 넣고 bfs를 돌리면된다. 시작점이 여러 개일 경우, 모든 시작점을 동시에 큐에 넣고 bfs를 수행하면 모든 시작점에서 동시에 확산하는것 처럼 작동하기때문에 시작점을 고민할 필요는없다.  소스코드#incl..

문제링크문제요약시작점 1번 에서 부터 시작하여 단방향 그래프를 더 이상 진행할 수 없을때 까지 탐색한다.이때 탐색과정에서 특정노드(팬클럽)을 만나게되면 "YES"를 출력 아니라면 "yes"를 출력하는 문제이다.어떻게 풀어야 할까그래프를 탐색해야하는데 이때 시작지점에서 끝지점까지 쭉 진행해야한다.즉, 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 알고리즘 dfs를 사용하는 문제이다.팬클럽을 만났을때를 제외하고 stack에 넣으면서 dfs를 하면된다.해당 분기를 끝났다는것은 vector에서 다음 간선이 없는 경우를 분기가 끝났다고 판단하였다.이 문제는 팬클럽을 안만는 "yes"의 경우를 찾는것이 핵심이니 단 한번이라도 팬클럽을 만나지 않는 순간 "..

문제링크문제요약단방향 그래프에서 시작지점 x를 주고 x에서 k만큼 떨어진 노드를 전부 출력하는 문제이다.k까지의 최단거리를 찾는것이니 dfs를 돌린후 거리가 k만큼 나오는것을 출력하면된다. 문제자체가 DFS의 대표문제이니 수도코드나 해결법에대해 따로 적지는 않았다.문제가 이해가 안간다면 dfs를 공부하고오는것이 좋다.소스코드#include #include using namespace std;/*단방향 그래프가 주어질때 거리계산bfs로 풀린텐데시간 복잡도는 괜찮을지 의문*/vector v[1000005];int vist[300005] = {0,};int n, m, k, x;int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >>..

[문제링크][https://www.acmicpc.net/problem/7562]문제요약체스판이 주어지고 나이트의 시작점과 목표하는 도착 지점이 주어진다. 나이트가 목표지점까지 도달하는 최소거리를 구하는 문제이다. bfs개념이 없다면 어떻게 풀어야 할지도 이해할 수 없을 것이다. 반면 bfs개념이 있다면 bfs를 사용하면 바로 해결되는 대표적인 dfs문제이다.어떻게 풀어야 할까2차원배열에서 나이트의 시작점을 큐에 넣고 dfs를 돌리면 해결된다. bfs 개념을 아는데 어떻게 해야 할지 잘 모르겠다면 코드를 보면서 이해하는 것도 좋은 방법이다.수도코드체스판을 2차원배열에 담는다.나이트는 8방향으로 움직일 수 있다. 8방향에 움직임에 대한 배열을 적어놓는다.방문을 기록하는 배열과 최단 거리를 적을 배열을 준비한..

문제링크문제요약한국인에게는 익숙한 촌수의 개념을 가져온 문제이다. 부모, 자식 관계가 나타난 그래프를 주고 입력에서 요구한 두 사람의 촌수를 구하면 되는 문제이다.어떻게 풀어야 할까이 문제는 부모-자식 간의 그래프가 있을 때 입력에서 요구한 두 사람의 촌수, 즉 최단 경로를 구하면 되는 문제이다. 최단경로문제이니 BFS를 사용하면 된다.헷갈렸던 부분부모와 자식 간의 방향이 단방향 그래프라고 생각하고 해결하려 했는데 입력에서 주어진 두 사람의 관계를 파악하기 위해서는 양방향 그래프로 입력을 받아야 했다. 그리고 queue에 넣을 때 depth 관한 부분도 같이 넣어줘 야했던 부분도 바로 생각이 안 나서 생각보다 시간이 오래 걸렸다.수도코드부모와 자식 간의 입력을 받고, 양방향 그래프로 저장한다.입력에서 요..

문제링크문제요약'A', 'E', 'I', 'O', 'U'이 글자로만 이루어진 최대길이 5자리짜리 단어사전이 있다. 'A' 단어가 단어장의 가장 처음에 나오고 그 다음엔 'AA', 'AAA', 'AAA', 'AAAA', 'AAAAA', 'AAAAE' ... 'UUUUU'로 이루어진 단어장이다. 입력으로 들어온 단어는 단어장의 몇번째인지를 출력하면 되는 문제이다.어떻게 풀어야 할까완전탐색을 통한 해결수학적 해결각 자리의 가중치를 미리 계산한다.주어진 단어의 각 자리에서 해당 가중치를 곱해 최종 위치를 계산한다.가중치 계산가중치 계산은 자리 수의 가중치를 통한 순서 계산 방법으로, 수열의 합을 이용한 간단한 등비수열의 합이다. 이 문제의 경우, 각 자리에 올 수 있는 문자가 5개 (A, E, I, O, U)이..

문제링크문제요약나무의 높이와 잘라서 가져가야 하는 나무의 길이 M이 주어진다. 나무를 자를 높이 H를 설정하면 일괄적으로 모든 나무를 H높이에서 잘라간다. 이때 가져가야하는 나무의 길이 M을 만족하는 최대의 높이를 구해야 한다.어떻게 풀어야 할까나무의 최대 수는 백만 개, 나무의 높이는 최대 1억까지 높아진다. 잘라야 하는 높이를 0부터 최대 1e9까지로 설정한 뒤 적절한 높이를 출력해야 하는데, 문제의 제한시간은 1초이기 때문에 0부터 1e9까지를 이진탐색으로 돌려 시간초과를 해결해야 한다.수도코드입력받기나무의 개수 N과 필요한 나무길이 M을 입력받는다.배열에 각 나무의 길이를 입력받는다.이진 탐색 초기화left = 0, right = 1e9으로 설정한다.이진 탐색 수행잘라낸 나무 길이 >= 필요한 나..

문제링크문제요약[[백준 - 24479]] 문제와 완전 똑같은 문제이다. 24479 문제는 dfs를 요구했지만 이번문제는 bfs를 요구한다.bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점 for each v ∈ V - {R} visited[v] 문제에서는 친절히 bfs의 기본형태를 제공해 준다. 따로 문제요약은 작성하지 않겠다. 24479와 완전히 똑같은 입력과 출력을 요구하고 안의 로직만 dfs, bfs 차이가 있으므로 링크로 대체한다.수도코드visited []을 준비한다. 원래는 bool타입의 visited []을 사용하는데 이 문제에서는 방문순서를 저장해야하기때문에 visited[]을 int로 설정해 0이면 방문하지않았음 1이상이면 방문했음을..

문제링크문제요약* 문제가 조금 난해하게 쓰여있는 것 같아 한줄한줄 해석하는 식으로 적었습니다.문제의 큰틀은 dfs를 돌렸을 경우 각 정점마다의 방문순서를 출력해 달라는 문제다,문제와 같이 기본적인 dfs의 형태도 같이 제시해주었는 이것이 이해가 안 된다면 dfs개념공부를 다시 하고 와야 한다.dfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점 visited[R] 이후 입력의 첫 번째 줄에 아래 3가지 정보를 주고,정점의 수간선의 수시작정점이후 간선의 수만큼 입력이 들어와 간선의 정보에 대해 알려주고 있다. 추가로 (u, v) 값의 쌍이 다르다 했으니 중복되는 간선은 주어지지 않는다.수도코드visited []을 준비한다. 원래는 bool타입의 visited []을..

문제링크문제요약심사를 받으려는 사람 n명과심사관의 정보가 담긴 times를 주어진다.times에서 알 수 있는 것은 두 가지이다.times.size(): 심사관의 수times: 각 심사관당 걸리는 시간n명이 모두 심사를 받는다고 할 때 걸리는 최소시간을 찾아야 한다. 어떻게 풀어야 할까입력되는 수를 보면 n은 최대 10억, 심사관이 걸리는 시간 또한 10억이다.최대시간은 10억 x 10억으로 1e18이 이 문제에서 나올 수 있는 가장 긴 시간이다. 걸리는 시간을 찾는다고 할 때 1부터 1e18로 찾는다면 시간초과가 발생하니 이 문제는 걸리는 시간을 이진탐색으로 찾아내야 한다. 수도코드left는 1로 right는 최댓값인 1e18로 설정한다.중간값 mid를 얻은 뒤 mid에 관한 시간 동안 심사관들이 몇 ..