알고리즘 문제풀이
-
[백준/BOJ] 13549번 숨바꼭질 3 (C++)알고리즘 문제풀이/백준 2020. 11. 29. 13:28
www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질 문제와 비슷한 BFS 문제 주의할 점은 이동의 순서를 순간이동 -> 뒤로 가기로 맞춰야 한다는 점입니다. #include #include #include #define MAX 200001 using namespace std; int n, k; int visit[MAX]; void BFS() { memset(visit, -1, sizeof(visit)); queue q;..
-
[백준/BOJ] 12851번 숨바꼭질 2 (C++)알고리즘 문제풀이/백준 2020. 11. 29. 13:27
www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 기존의 숨바꼭질 1에서는 visit 배열을 int로 선언하여 큐가 진행되면서 최소 시간을 기록했지만, 여기서는 최소 시간이 똑같이 나오는 경우의 개수도 출력해야하기 때문에 visit 배열을 bool로 선언하고, 큐가 pop을 하고 난 후 방문 처리를 해 중복 방문이 가능하게 만들었습니다. 처음에 동생을 만난 경우와 이후에 동생을 만난 경우를 구분하기 위해 cnt가 0일때 동..
-
[백준/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..
-
[프로그래머스/Level 3] 단어 변환 (C++)알고리즘 문제풀이/프로그래머스 2020. 11. 24. 17:19
programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 레벨3 문제 치고는 어렵지 않은 DFS/BFS 문제였습니다. begin 문자열이 words 배열의 문자열중 어느 문자열로 바뀔 수 있는지를 잘 구현만 한다면 쉽게 해결할 수 있을 것 같습니다. /* BFS 풀이 */ #include #include #include #include using namespace std; bool visi..