분류 전체보기
-
[백준/BOJ] 7569번 토마토 (C++)알고리즘 문제풀이/백준 2021. 1. 14. 19:31
www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net BFS 유형의 문제입니다. 7576번 문제가 3차원으로 바뀐 문제입니다. #include #include #include #include using namespace std; int m, n, h; int map[101][101][101]; int visit[101][101][101]; int dz[6] = {1, -1, 0, 0, 0, 0}; int dx[6] = {0, 0, 1, -1..
-
[백준/BOJ] 1012번 유기농 배추 (C++)알고리즘 문제풀이/백준 2021. 1. 14. 18:21
www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 전형적인 BFS 유형의 문제였습니다. 세로의 길이를 먼저 입력받는 것을 주의 #include #include #include #include using namespace std; int map[51][51]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; void BFS(int sx, int sy, int m, int n) { queue q; q.push({ sx, sy }..
-
[백준/BOJ] 16940번 BFS 스페셜 저지알고리즘 문제풀이/백준 2021. 1. 14. 17:29
www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 처음보는 유형의 BFS 문제였습니다. (다시 풀기) 양방향 그래프를 만들고, 마지막 줄의 BFS의 방문순서를 큐에 저장합니다. 현재 정점과 인접한 정점들을 BFS 탐색하기 전에, set에 넣어주어 아까 큐에 저장했던 방문순서의 front 값이 set에 저장되어있는지 확인하는 것이 포인트입니다. #include #include #include #include using namespace std; vector graph[100001]; queue input; // 입력으로 받은 방문 순서가 저장된 큐 bool visit[10000..
-
[백준/BOJ] 4179번 불! (C++)알고리즘 문제풀이/백준 2021. 1. 13. 19:52
www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 조금 색다른 유형의 BFS 문제 유형이었습니다. BFS를 두번 진행해야하는데, 먼저 불의 BFS를 진행하여 불의 확산시간을 fvisit 배열에 기록하고, 다음에 지훈 BFS를 진행하여 불의 확산시간과 비교하면서 이동시간을 기록합니다. 지훈이가 특정 위치에 이동하기 위해선 불의 확산이 진행되지 않은 곳이거나, 그 위치에서의 불의 확산 시간과 지훈이의 이동시간을 비교해 불의 확산시간이 더 커야 이동할..
-
[백준/BOJ] 7576번 토마토 (C++)알고리즘 문제풀이/백준 2021. 1. 13. 18:29
www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net BFS 유형의 문제입니다. 토마토가 있는 위치를 벡터에 담아서 큐에 넣어줬습니다. 큐가 진행되면서 visit 배열에 최소 일수가 기록됩니다. 예외처리만 제대로 해준다면 어렵지 않은 문제였습니다. #include #include #include #include using namespace std; int m, n; int map[1001][1001]; int visit[1001][1001]; in..
-
[백준/BOJ] 2251번 물통 (C++)알고리즘 문제풀이/백준 2021. 1. 13. 17:30
www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net BFS 유형의 문제였습니다. (다시 풀기) 세개의 물통이 있을 때, 한 물통에서 다른 하나의 물통으로 물을 쏟아붓는 경우의 수는 다음과 같습니다. a->b a->c b->a b->c c->a c->b 위의 6가지 경우를 BFS를 탐색해주는데, 이때 두가지 경우를 고려해줘야합니다. 1. 비우는 물통의 물 양 + 채우는 물통의 물 양 > 채우는 물통의 크기 2. 비우는 몰통의 물 양 + 채우는 ..
-
[프로그래머스/Level 2] 이진 변환 반복하기 (C++)알고리즘 문제풀이/프로그래머스 2021. 1. 13. 15:56
programmers.co.kr/learn/courses/30/lessons/70129 코딩테스트 연습 - 이진 변환 반복하기 programmers.co.kr 1. 무한루프 안에서 문자열 s의 모든 0을 제거합니다. 2. 제거할 때마다 제거한 횟수를 더해줍니다. 3. 0이 제거된 문자열의 길이를 2진수로 변환해줍니다. 4. 변환이 끝나고 변환한 횟수를 더해줍니다. 5. 이러한 과정을 문자열의 길이가 1이 될 때까지 반복합니다. #include #include using namespace std; string getBinary(int num) { string strBinary = ""; while(1) { if(num == 0) break; strBinary.insert(0, to_string(num % ..
-
[백준/BOJ] 16947번 서울 지하철 2호선 (C++)알고리즘 문제풀이/백준 2021. 1. 12. 16:46
www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 그래프 + DFS + BFS 유형의 복합적인 문제입니다. (다시 풀기) 먼저 순환선을 이루는 역을 알아내기 위해서 사이클을 만들어내는 정점을 찾아내야 하는데, DFS를 통해 탐색하다가 처음 시작 위치로 돌아오는 경우를 찾으면 됩니다. (16929번 문제와 비슷합니다.) 이러한 탐색을 1번 정점 ~ n번 정점까지 실행하면서 체크를 한 후, 사이클이 아닌 정점만 따로 BFS를 통해 사이클..