컴맹에서 개발자 되기

백준 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층으로 이동하려고 한다. 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베..

백준 1475번 방 번호 간단한 배열 문제이지만, 정답률이 30퍼대로 낮은 문제이다. 숫자가 부족하면 채우는 것이 아닌, 최대 까지 채워진 숫자 세트에서 필요한 만큼 가져다가 쓰면 되는 문제다. https://www.acmicpc.net/problem/1475 풀이방법 1) 크기(size)가 10 이고 값(value)이 1,000,000인 check 배열을 생성한다. 이유는 N의 최대값이 1,000,000이기 때문이다. 2) check배열을 생성한 이유는 입력받은 string에 해당하는 숫자를 발견한다면, 해당 check 배열에 index에 접근해 값을 -1 해줄 것이다. 3) 입력받은 string 값의 해당하는 숫자를 발견한다면, 6인지 9인지 구별한다. 구별한 뒤, 더 값이 큰 쪽에 -1 를 해준다...

백준 14891번 톱니바퀴 전형적인 시뮬레이션 문제이다. 2차원 배열을 더 쓰면 간단하게 할 수 있지만, 4개 밖에 되지 않아 하드 코딩했다. https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다. 다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴 www.acmicp..

백준 11559번 Puyo Puyo 전형적인 시뮬레이션 문제이다. https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net 풀이방법 1) R, G, B, P, Y 순으로 BFS를 통해 4개가 뭉쳐있는 곳을 찾아 check2배열에 표시해놓는다. 2) 터트린 부분을 위에서 부터 밑으로 한칸 씩 채운다. 함수 설명 bfs() : bfs 탐색 move_block(int x, int y): y열에서 x칸까지 1칸씩 이동 delete_block(): 몇 번 이동할지 결정 ※주의사항: BFS할 때 위에서 한번만 훝는 씩이 아닌 각각 색깔에 대한 검사가..