프로그래밍
BOJ 14226 · 이모티콘
알고리즘 분류 : BFS S개의 이모티콘을 화면에 만드는 데 걸리는 최소 시간을 구하는 문제다. 3개의 동작이 있고, 각 동작은 1초가 걸리며, 이 동작의 최소 횟수를 구하는 문제이므로, BFS 풀이로 접근할 수 있다. 방문(상태) 체크를 하기 위해서, 2차원 배열이 필요하다.2차원 배열의 인덱스는 [화면에 있는 이모티콘] [클립보드에 있는 이모티콘] 이다.화면에 있는 이모티콘을 x, 클립보드에 있는 이모티콘을 y라 했을 때, 현재 상태를 (x, y)라 하자.다음 상태는 다음과 같다.1. 복사 (x, x)2. 붙여넣기 (x+y, y)3. 삭제 (x-1, y)위 3가지를 기준으로 BFS를 돌려서 최소 시간을 구하면 된다. C++ 소스코드 #include #include using namespace std;..
BOJ 15666 · N과 M (12)
알고리즘 분류 : 브루트 포스 입력받은 N개의 숫자 중에서 M개를 뽑아서 출력하는 문제다. N과 M (8) 문제와 비슷하나, N개의 숫자 중 중복된 숫자가 주어질 수 있다. N과 M (11) 문제에서 for문의 시작 지점만 바꾸면 된다. C++ 소스코드 #include #include #include using namespace std; int n, m; vector a, v; void solve(int cnt, int idx) { if (cnt == m) { for (auto k : v) printf("%d ", k); printf("\n"); return; } for (int i=idx; i
BOJ 15665 · N과 M (11)
알고리즘 분류 : 브루트 포스 입력받은 N개의 숫자 중에서 M개를 뽑아서 출력하는 문제다. N과 M (7) 문제와 비슷하나, N개의 숫자 중 중복된 숫자가 주어질 수 있다. 중복된 수를 제거하고 (7) 문제와 비슷하게 그대로 돌리면 된다. C++ 소스코드 #include #include #include using namespace std; int n, m; vector a, v; void solve(int cnt) { if (cnt == m) { for (auto k : v) printf("%d ", k); printf("\n"); return; } for (int i=0; i
BOJ 15664 · N과 M (10)
알고리즘 분류 : 브루트 포스 입력받은 N개의 숫자 중에서 M개를 뽑아서 출력하는 문제다. N과 M (6) 문제와 비슷하나, N개의 숫자 중 중복된 숫자가 주어질 수 있다. 중복을 제거하는 방법은 N과 M (9) 문제와 동일하게 처리하면 된다. C++ 소스코드 #include #include #include #include using namespace std; int n, m; bool check[8]; int a[8]; vector v; set s; void solve(int cnt, int idx) { if (cnt == m) { s.insert(v); return; } for (int i=idx; i
BOJ 15663 · N과 M (9)
알고리즘 분류 : 브루트 포스 입력받은 N개의 숫자 중에서 M개를 뽑아서 출력하는 문제다. N과 M (5) 문제와 비슷하나, N개의 숫자 중 중복된 숫자가 주어질 수 있다. 같은 숫자가 여러 개 주어질 수 있으므로, 해당 숫자가 총 몇 개 있는지 세어야 한다.먼저 N개의 숫자가 있는 리스트를 오름차순으로 정렬한다.숫자 리스트에서 처음부터 끝까지 순서대로 이동하면서 각 숫자가 몇 개 있는지 센다.숫자를 세는 방법은 아래와 같다.1. 현재 숫자가 이전 숫자와 같으면, 중복된 숫자이므로 현재 숫자의 개수를 1 증가시킨다.2. 현재 숫자가 이전 숫자와 다르면, 새로운 숫자이므로 숫자 카운트를 1로 둔다. 이전에 카운트한 숫자의 값을 저장한다. C++ 소스코드 #include #include #include us..
BOJ 4179 · 불!
알고리즘 분류 : BFS 불이 도달하기 전에 탈출하는 최단 거리를 구하는 문제다. BOJ 5427번 문제 '불'과 유사하다. 불의 좌표를 먼저 큐에 집어 넣는다. 여러 곳이 있을 수 있으며, 모두 먼저 넣어야 한다.불 좌표를 모두 넣었다면, 이후에 사람 좌표를 넣는다.BFS 탐색 시작. C++ 소스코드 #include #include using namespace std; struct fire { int x, y, f; }; int R, C, sx, sy; char a[1000][1000]; int dist[1000][1000]; queue q; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; void bfs() { q.push({sx, sy, 0}); di..
BOJ 14503 · 로봇 청소기
알고리즘 분류 : 시뮬레이션 로봇이 청소할 수 있는 영역의 최대 개수를 구하는 문제다. 문제의 조건을 그대로 구현하면 된다. 방향은 북(0), 동(1), 남(2), 서(3) 순서로 둔다.로봇은 왼쪽으로만 돌기 때문에, 북(0)→서(3), 동(1)→북(0), 남(2)→동(1), 서(3)→남(2)으로 방향이 바뀐다.따라서 방향 전환은 (다음 방향) = (현재 방향 + 3) % 4 로 나타낼 수 있다.입력에서 청소되지 않은 칸은 (0), 벽은 (1)로 주어지므로, 이를 구분하기 위해 청소한 칸은 (2)로 바꾼다.1. 위에 주어진 데로 4번 회전을 하면서 청소가 가능한 칸이 있는지 확인한다.2. 청소할 수 있다면, 그 칸으로 전진하고 방향은 왔던 방향을 유지한다. 과정 1번부터 다시 반복한다.3. 한 칸도 청소..
BOJ 1726 · 로봇
알고리즘 분류 : BFS 로봇이 출발 지점에서 도착 지점까지 이동하기 위해 필요한 최소 명령 횟수를 구하는 문제다. BFS를 통해 최단 거리를 구하는 문제인데, 방향 전환 명령과 이동 명령이 구분되어 있어서 까다롭다. 이동 명령을 먼저 내리고, 그다음에 방향 전환 명령을 내리는 흐름으로 짜야 한다.Queue에는 3가지 정보를 넣어야 한다. 그 정보는 'x좌표, y좌표, 현재 방향'이다.방문 여부를 확인하고, 명령 횟수를 저장할 배열 'dist' 를 3차원 배열로 선언한다. 인덱스는 큐에 들어가는 정보와 같다.이동 명령은 1, 2, 3 거리로 이동할 수 있으므로, 1칸 이동부터 3칸 이동 순으로 진행한다.이동할 때 만약 앞에 벽이 있다면 곧바로 for 문을 break 한다. 짧은 거리를 못 가면, 더 긴 ..