전체 글
[백준] 자동차경주대회
https://www.acmicpc.net/problem/2651 2651번: 자동차경주대회 첫째 줄에는 정비를 받지 않고 갈 수 있는 최대 거리가 주어진다. 둘째 줄에는 정비소의 개수가 입력되는데 정비소 수는 100개 이하이다. 셋째 줄에는 인접한 정비소 사이의 거리가 차례로 주어 www.acmicpc.net BFS를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 출발지와 도착지 사이에 정비소들이 있고, 각 정비소들은 정비시간을 가집니다. 자동차는 한 정비당 갈 수 있는 거리가 정해져 있습니다. 이 때, 총 정비시간을 최소화 해서 도착지점에 도착 했을 때, 거친 정비소, 정비소 갯수, 걸린 시간을 출력해야 합니다. 매번 출발지가 있을 것입니다. 처음에는 출발위치에서 출발할 것이고, 이후에는 정..
[백준] 모래성
https://www.acmicpc.net/problem/10711 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net BFS를 이용하는 문제입니다. 문제부터 간단하게 요약해보면, 모래성이 있고, 파도가 치는 상황이 주어집니다. 매 파도가 칠 때, 파도와 가로 세로 대각선으로 닿는 부분이 강도보다 크거나 같은 경우 무너지게 됩니다. 이 때, 총 몇번의 파도가 몰려오고 나서 모래성이 수렴하는지를 구해야 하는 문제입니다. queue에 파도를 넣어 bfs를 이용하면 됩니다. 이 때, 몇번 파..
[백준] 영역 구하기
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net DFS를 이용한 floodfill 기본문제입니다. 우선 문제부터 간단하게 요약해보면, 모눈종이에 검정색 직사각형들이 그려져 흰 구역들이 분리가 되게 됩니다. 이 때, 분리되어 나누어지는 영역의 개수와, 각 영역의 넓이를 오름차순으로 정렬하여 출력하는 문제입니다. 모눈종이에 검정색 영역들을 먼저 모두 채웁니다. 다음으로 흰 영역에서 floodfill하여 영역의 크기를 계산해줍니다..
[백준] Puyo Puyo
https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 구현, 시뮬레이션 문제입니다. 문제부터 간단하게 요약하면, 애니팡 같이 뿌요뿌요라는 게임이 있습니다. 이 게임에서는 뿌요들이 4개이상 모이면 폭발하는데 매번 터질수 있는 푸요들이 모두 터진후 뿌요들이 내려옵니다. 그리고 또 다시 터질 것이 있다면 상태가 변화하지 않을 때 까지 반복됩니다. 이 반복이 총 몇번 일어나는지를 계산해 주는 것을 구현해야 합니다. - 푸요의 폭발 ..
[백준] Tractor
https://www.acmicpc.net/problem/5846 5846번: Tractor One of Farmer John's fields is particularly hilly, and he wants to purchase a new tractor to drive around on it. The field is described by an N x N grid of non-negative integer elevations (1 N; for (int i=0; i grids[i][j]; } } } int abs(int k){ return (k>=0)? k : -k; } void fill(int r, int c, int mid){ // bfs로 채우자 queue q; q.push((rc){r,c}); vi..
[백준] 색종이 - 2
https://www.acmicpc.net/problem/2567 2567번: 색종이 - 2 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 구현 문제입니다. 우선 문제부터 간단하게 설명해보면, 100x100의 하얀 도화지 위에 검정 종이들을 붙입니다. 이 때, 검은 영역의 둘레 길이를 출력해야 합니다. 저의 구현의 경우 하얀 부분을 쭉 채워나가면서, 검정 경계선을 만났을 때 카운팅을 하는 방식을 사용하였습니다. 흔히 flood fill 이라 불리는 풀이방식을 사용하였습니다. 내부의 둘레도 둘레에 포함시켜야 하므로 for loop로..
[정올] 미로탈출 로봇중간 단계
http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=521&sca=99&page=3 JUNGOL www.jungol.co.kr 구현문제 입니다. 우선 문제부터 간단하게 요약하면, 로봇의 규칙과 미로가 주어질 때, 해당하는 규칙으로 로봇이 최대로 이동할 수 있는 거리를 출력하면 됩니다. 구현 문제이므로 문제의 조건에 알맞게 구현을 하면 됩니다. 한번 지나간 길을 다시 지나갈 수 없다 등의 조건이 있으니, 중간중간에 확인을 올바르게 해주어야 함을 주의해서 코드를 구성하면 됩니다. 실제 구현은 아래와 같습니다. #include using namespace std; #define MAXN (10) int N; char map[MAXN + 10][MAXN + 10];..
[정올] 회의실 배정
http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=645&sca=50&sfl=wr_hit&stx=1370&sop=and JUNGOL www.jungol.co.kr 기본적인 그리디 문제입니다. 문제부터 요약하면, 회의를 최대한 안겹치게 개최할 때, 회의 갯수와 어떤 회의들이 개최 되었는지를 출력해야 합니다. 회의 종료시간을 기준으로 sorting하여 greedy를 이용하여 구현하면 됩니다. 실제 구현은 아래와 같습니다. #include #include using namespace std; int N; struct meeting{ int id, start, end; }meetings[500]; int ids[500]; void getinput(){ cin >>..