0과 1의 쉼터

문제https://www.acmicpc.net/problem/6593풀이L, R, C로 이루어진 직육면체에서 상하좌우, 위, 아래로만 이동하며 출발지 S에서 도착지 E로 도착하는데 걸리는 최단 시간을 구하는 문제다.BFS를 3차원으로 확장하면 되는 기본 문제다.우선 시작 전 문자나 상태를 정의해주자.상위 그래프 문제로 갈수록 이처럼 문제에서 주어지는 문자들을 자신의 언어로 변환해주는게 실수를 방지하는데 도움이 된다.L, R, C가 모두 0이 아닐 때 까지 입력을 받으며 탐색을 진행하면 된다.그래프 정보를 입력받으며 벽을 표시해주고, 시작점과 종료점의 위치를 파악해주자.(sl, sr, sc, el, er, ec)각 층마다 한 줄 공백 입력이 주어진다는 점에 유의하자.기본 BFS를 3차원으로 확장해 구현해주..

문제https://www.acmicpc.net/problem/2583풀이K개의 직사각형을 제외한 나머지 영역의 개수와 넓이를 구하는 문제다.우선 문제의 예제를 살펴보자.K개의 직사각형에 대해 표시하면 다음과 같다. 왼쪽아래 좌표와 오른쪽위 좌표가 주어지는데 그림을 회전시켜보자.일반적인 배열의 논리적 표현과 같다.그러면 사각형의 넓이는 어떻게 구할까?전체적으로 행과 열을 축소시키면 된다.즉, 이 문제에서 다룰 범위는 M, N에 대해 (0, 0) ~ (N - 1, M - 1)가 된다.K개의 좌표를 입력받아 블럭표시를 해주자.이제 블럭( BLCOK )이 아니고, 방문한적 없는( EMPTY )영역들에 대해 BFS를 진행하면된다.bfs(i, j)는(i, j)에서 bfs를 하고, 하나로 연결된 영역의 넓이를 반환한..

문제https://www.acmicpc.net/problem/17071풀이수빈이와 동생이 각각 N, K에서 이동할 때 몇 초 후에 서로 만날 수 있는지 계산하는 문제다.수빈이는 다음과 같이 움직일 수 있다.X - 1X + 12X동생은 다음과 같이 움직일 수 있다.N + KK는 경과 시간이자. 동생이 움직일 수 있는 거리를 의미한다. 풀이에서는 step으로 표현하겠다.만약 N == K인 경우 수빈이와 동생은 제자리에서 만나므로 탐색이 불필요하다. 걸린 시간은 0초다.bfs로 N부터 탐색을 시작하자.큐가 비어있거나, k(동생의 이동 위치)가 500,000이하라면 탐색을 계속해야 하므로 동생의 이동거리부터 계산하며 조건식에 포함시켜주자.본격적으로 풀이를 하기전에 시간복잡도에 대해 생각해보자.수빈이는 X - 1..

문제오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 만들어 지는 트리를 너비 우선 탐색 트리라고 하자. 너비 우선 탐색 트리에 있는 i번 노드의 깊이(depth)를 di라고 하자. 시작 정점 R의 깊이는 0이고 방문 되지 않는 노드의 깊이는 -1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 i번 노드의 방문 순서를 ti라고 하자. 시작 정점의 방문 순서는 1이고 시작 정점에서 방문할 수 없는 노드는 0..

문제오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 만들어 지는 트리를 너비 우선 탐색 트리라고 하자. 너비 우선 탐색 트리에 있는 모든 노드의 깊이(depth)를 출력하자. 시작 정점 R의 깊이는 0이고 방문 되지 않는 노드의 깊이는 -1로 출력하자.너비 우선 탐색 의사 코드는 다음과 같다. bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점  for each v ∈ V - {R}..

문제오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 내림차순으로 방문한다.bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점  for each v ∈ V - {R}  visited[v] 입력첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤..

문제오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점  for each v ∈ V - {R}  visited[v] 입력첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤..

문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.입력첫째 줄에 1보다 크거나 같고, 10^18보다 작거나 같은 정수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.풀이X가 최대 10^18이므로 기존의 DP 방식 풀이가 불가능하다.Queue와 HashMap을 사용해 풀이할 수 있다.Queue만 사용하면 시간 초과가 발생할 것이다. Dictionary에 이미 계산된 x에 대해 연산 횟수를 기록해주자.최소 연산 횟수를 저장할 visited를 선언해주자..

문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.풀이아래 문제의 확장판이다. [백준 01463] 1로 만들기 [C/C++]문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으..

문제뿌요뿌요의 룰은 다음과 같다.필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다.뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.남규는 최근 뿌요뿌요 게임에 푹 빠졌..