알고리즘 문제풀이/백준
-
[백준/BOJ] 1697번 숨바꼭질 (C++)알고리즘 문제풀이/백준 2020. 11. 29. 13:26
www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS 기초 문제 처음 수빈이의 위치에서 뒤로가는 경우, 앞으로 가는 경우, 순간이동 하는 경우를 계속 큐에 넣어가며 동생의 위치와 같아지는 순간을 구하여 그 시간을 출력한 후 종료 #include #include #include #include using namespace std; int n, k; int visit[100001]; void BFS() { queue q; q.push..
-
[백준/BOJ] 3197번 백조의 호수 (C++)알고리즘 문제풀이/백준 2020. 11. 27. 13:44
www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 각 R줄 동안 C만큼의 문자열이 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 어려운 BFS 문제, 푸는데 3~4시간 걸렸다. 근데 시간이 이정도로 오래 걸린건 어려워서 그런게 아니라 "map[nx][ny] = '.';" 요 부분을 "map[nx][ny] == '.';" 이렇게 써가지구 자꾸 답이 이상하게 나왔다. SIBAL (다시풀기) 풀이는 일반적인 BFS 방법을 사용하면 시간초과가 발생한다. BFS 탐색에서의 시간을 줄이기 위해서 백조를 탐색할 때 기존에 체크했던 배열을 그..
-
[백준/BOJ] 16987번 계란으로 계란치기 (C++)알고리즘 문제풀이/백준 2020. 11. 27. 00:39
www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 처음보는 유형의 DFS + 구현 문제인데 일단 문제 자체가 이해가 잘 안가고 개인적으로 어려웠던 문제 내구도와 무게를 배열을 두어 입력받는것 과 계란을 깼는지 안깼는지 확인하는 flag 변수를 두는 것이 포인트 #include #define MAX 9 using namespace std; int s[MAX], w[MAX]; int n, answer; void DFS(int idx) { // 계란을..
-
[백준/BOJ] 1600번 말이 되고픈 원숭이 (C++)알고리즘 문제풀이/백준 2020. 11. 26. 14:19
www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 그렇게 어렵진 않은 BFS 문제였습니다. 나이트 이동 여부를 체크하기 위해 3차원 체크 배열을 사용하는 것이 문제의 포인트였던 것 같습니다. #include #include #define MAX 201 using namespace std; int map[MAX][MAX]; bool visit[MAX][MAX][MAX]; // x, y 좌표와 나이트 이동 여부를 체크 int dx[4] = {1, ..
-
[백준/BOJ] 6593번 상범 빌딩 (C++)알고리즘 문제풀이/백준 2020. 11. 26. 11:54
www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net BFS 문제인데 입력 배열이 3차원이라는 특징이 있습니다. 7569번 3차원 토마토 문제와 비슷해서 쉽게 해결할 수 있었습니다. (토마토 문제가 오히려 더 예외처리가 많아서 어려웠던 느낌) #include #include #include #define MAX 31 using namespace std; int c, r, l; char map[MAX][MAX][MAX]; int visit[MAX][MAX][MAX]; i..
-
[백준/BOJ] 5427번 불 (C++)알고리즘 문제풀이/백준 2020. 11. 24. 10:54
www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net BFS 문제 유형중 하나입니다. 문제를 해결하는 불의 확산과 상근이의 이동을 체크할 수 있는 배열을 각각 선언하고, 각각의 BFS를 구현 하는 것입니다. BFS가 진행되면서 각각의 배열인 fire와 visit에 시간이 기록됩니다. 여기서 구하는 시간은 상근이가 나중에 이동을 할 때 해당 케이스에서 빠져나갈 수 있는지 없는지를 결정하는 중요한 요소가 됩니다. (아래 코드의 주석을 참고하시면 될 것 같습니다.) #include..
-
[백준/BOJ] 10026번 적록색약 (C++)알고리즘 문제풀이/백준 2020. 11. 23. 17:17
www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 난이도가 쉬운 BFS 문제였습니다. 적록색약이 아닌 사람이 봤을 때 구역의 총 개수를 먼저 구한 후, 색의 입력을 받은 map 배열에서 G의 값을 전부 R로 바꾸어 적록색약인 사람이 봤을 때 구역의 총 개수를 구하면 되는 문제입니다. #include #include #include #include #include using namespace std; int n, first, second; char map..
-
[백준/BOJ] 9466번 텀 프로젝트 (C++)알고리즘 문제풀이/백준 2020. 11. 23. 12:43
www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net BFS로 풀다가 시간 초과 때문에 2시간 날린 문제 ... (다시 풀기) lmcoa15.tistory.com/51 백준 9486번 - 텀 프로젝트 https://www.acmicpc.net/problem/9466 그래프 문제 중에서 사이클에 대한 개념을 알고 있는지에 대한 문제이다. 학생들이 함께 프로젝트를 하고 싶은 학생을 가리키고 있을 때 사이클에 대한 개수가 몇 개 lmcoa15.tistory.com 결국 구글..