컴맹에서 개발자 되기

백준 9466번 텀 프로젝트 시간초과에 주의해야되는 문제이다. https://www.acmicpc.net/problem/9466 풀이 방법 1) 한번에 탐색만에 사이클이 있고, 없고를 판단하면서 지나가야한다. 2) 1->2->3->4->5->4 라는 것이 있으면 4,5가 사이클이다. 여기서 4,5가 사이클임을 파악해야되고, 6번으로 바로 넘어가야 시간초과가 뜨지 않는다. #include #include #include #include using namespace std; int ans; int visited[100000]; //방문횟수 담는 배열 bool check[100000]; // 사이클을 찾았다는 뜻 int student[100000]; int T, number; void input_data() ..

백준 6593 상범 빌딩 3차원 bfs문제이다 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서 www.acmicpc.net 풀이 방법 1) bfs로 해결하면 된다. 2) 큐, 배열 초기화 잊지 말자 ! #incl..

백준 2146번 다리 만들기 BFS로만 풀 수 있지만, DFS와 BFS 둘 다 이용할 수 있는 문제이다. https://www.acmicpc.net/problem/2146 풀이방법 1) 각 나라를 구분짓기 위해 bfs나 dfs를 사용한다. 나는 bfs를 사용했다. 2) 각 나라를 구분지은 후, 나라와 나라 사이의 최단거리를 BFS로 구한다. 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 ..

백준 13913 숨바꼭질4 https://skd03052.tistory.com/150 의 응용문제이다. bfs와 역추적이 필요하다. https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 www.acmicpc.ne..

백준 13549 숨바꼭질3 bfs 문제이다. 기존 숨바꼭질과 로직이 살짝 다르다. https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 www.acmicpc.net 풀이방법 1) 순간이동의 시간은 0초니깐 순간이..

백준 5427번 불 BFS + 시뮬레이션 문제이다. 이런 문제는 실수가 종종 나와서 시간을 많이 잡아먹는다. https://www.acmicpc.net/problem/5427 풀이방법 1) 최단 거리를 찾아야함으로 bfs를 쓴다. 2) 불이 먼저 붙고, 사람이 먼저 움직인다. 3) 불에 대한 bfs - > 사람에 대한 bfs를 사용한다. 4) q의 사이즈를 이용하여 bfs 한다. 함수 설명 1) input_data() : 입력 받는 함수 , 이때 큐에 값을 push 해주는 것이 중요하다. (시간 단축) 2) bfs(): 불에 대한 bfs, 사람에 대한 bfs가 순차적으로 이뤄진다. 큐 사이즈를 이용해서 bfs를 진행시키면 되고, 사람bfs에서 범위를 나갔을 때 탈출한 것이라고 가정하면 된다. 3) sol..

백준 3055번 탈출 BFS + 시뮬레이션 문제였다. https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나 www.acmicpc.net 풀이 방법 1) 시뮬레이션을 생각하면, 고슴도치 이동 - > 물이 차오름, 을 구현하면..

백준 10870번 피보나치 수 재귀문제이다. https://www.acmicpc.net/problem/10870 풀이방법 1) 재귀 함수는 탈출 조건이 필요하다. 2) 피보나치 수열은 N이 0, 1, 2일때 탈출조건을 걸어주고, 재귀를 돌리면 된다. #include #include #include #include #include using namespace std; int N; int fib(int N) { if (N == 0) return 0; else if (N == 1 || N == 2) return 1; else { return fib(N - 1)+fib(N - 2); } } int main(void){ cin >> N; cout

백준 7569번 토마토 BFS 문제이다. https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마 www.acmicpc.net 풀이방법 1) 높이가 있어서 3차원배열이라고 생각하면 된다. 2) x,y,z가 담긴 구조체를 만들..

5014번 스타트링크 간단한 BFS 문제이다. https://www.acmicpc.net/problem/5014 풀이방법 1) BFS 탐색중 F보다 클 수 없고, 0보다 작을 순 없다. 2) check2라는 배열을 통해 몇 번째에 찾았는지 검색을 해줬다. 5014번: 스타트링크 문제 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다. 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베..