전체
BOJ 1743 · 음식물 피하기
알고리즘 분류 : DFS, BFS 음식물 덩어리의 최대 크기를 구하는 문제다. 간단한 플러드 필 문제이다. N*M 사이즈의 맵을 만들고 0으로 모두 채운다.입력으로 주어지는 음식물의 위치를 맵에 1로 채운다.음식물(1)을 기준으로 DFS 또는 BFS 탐색을 하여 연결된 음식물을 찾는다.가장 큰 음식물을 정답으로 낸다. C++ 소스코드 #include int n, m, k, ans; int a[100][100]; bool check[100][100]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; int dfs(int x, int y) { int ret = 1; check[x][y] = true; for (int i=0; i
BOJ 16946 · 벽 부수고 이동하기 4
알고리즘 분류 : DFS, BFS 벽 부수고 이동하기 네 번째 문제다. 이번 문제는 이전 문제들과 완전히 다르다. 플러드 필 알고리즘을 구현하는 문제이다. 기본 아이디어기본적으로, 각 벽(1)부터 DFS를 시작하여 빈칸(0)을 향해 뻗어나가는 방식을 생각할 수 있다.구현은 간단하지만, 최대 1000*1000 사이즈가 입력으로 주어지므로 시간 초과가 난다. 개선 아이디어배열 A를 DFS를 통해 완전 탐색한다.1. 빈칸(0)부터 시작하여 인접한 빈칸의 개수를 모두 세면서 리스트 V에 기록해둔다.2. 빈칸의 개수를 셀 때, 배열 B에 각 빈칸마다 넘버링을 해둔다.1~2 과정을 맵 전체에 한다.배열 A에서 각 벽(1)마다 인접한 4칸을 확인하고, 배열 B를 통해 저장해둔 넘버링이 있는지 확인한다.Set 자료구조..
BOJ 16933 · 벽 부수고 이동하기 3
알고리즘 분류 : BFS 벽 부수고 이동하기 시리즈 세 번째 문제이다. 이번에는 이동할 때 낮과 밤이 매번 바뀌고, 낮에만 벽을 부술 수 있다.BOJ 14442번 '벽 부수고 이동하기 2' 문제에서 낮과 밤 설정을 추가하여 구현하면 된다. check 배열을 통해 방문 여부 체크를 한다. 3차원 인덱스는 각각 [X 좌표] [Y 좌표] [벽 부순 횟수] 이다.낮부터 시작하며, 큐에서 모든 좌표를 꺼낸 후에 낮과 밤을 바꾼다. 다음 이동 좌표가 빈칸(0)인 경우1. 아직 방문하지 않은 곳이라면, 이동거리를 +1 증가시키고 이동한다.2. 벽 부순 횟수는 업데이트하지 않는다. 다음 이동 좌표가 벽(1)인 경우1. 벽 부순 횟수가 K 이하이며, 아직 방문하지 않은 곳이라면, 낮인지 밤인지 확인한다.2. 낮인 경우,..
BOJ 17086 · 아기 상어 2
알고리즘 분류 : BFS 아기 상어와의 거리를 구하는 문제다. BOJ 17086번 아기 상어와는 완전히 다른 문제다. 각 좌표에서 아기 상어와 떨어진 거리가 안전거리이며, 안전거리의 최댓값을 구해야 한다. 맵을 입력받으면서 상어의 위치(1)가 주어지면, 큐에 모두 집어넣는다.각 상어 위치부터 BFS 탐색을 하면서, 빈칸(0)이면 이동하면서 이동거리를 맵에 저장한다.맵을 완전 탐색한 후, 맵에 저장된 최댓값이 안전거리의 최댓값이 된다.거리를 1부터 시작했기 때문에, 정답은 위에서 구한 최댓값에 1을 빼야 한다. ✓ 1번 예제 테스트케이스를 설명하는 그림이다. 각 상어 위치(초록색)부터 BFS를 시작하면, 오른쪽 상태처럼 된다. C++ 소스코드 #include #include using namespace s..
BOJ 5373 · 큐빙
알고리즘 분류 : 시뮬레이션 루믹스 큐브의 회전을 주어진 조건 그대로 구현하는 문제다. 큐브의 좌표를 적당히 설정해서 회전하면 된다. 번뜩이는 아이디어가 떠오르지 않아서 무식하게 구현했다. 배열 인덱스가 꼬이기 십상인지라, 상당히 번거롭고 귀찮은 문제다. 큐브를 적당히 고정해놓고 좌표를 설정한다.각 면에 인덱스를 0~5까지 붙였다.3차원 배열 cube의 인덱스는 [면 번호] [서브 사각형 X좌표] [서브 사각형 Y좌표] 이다.각 면은 3*3의 서브 사각형으로 이루어져 있으며, 각 좌표는 (0,0)부터 (2,2)까지이다.아래 그림에서 각 면에 있는 검은색 점은 (0,0)의 위치다.각 면을 정면으로 바라보는 기준으로 회전을 시키면서 좌표의 변화를 업데이트해야 한다. C++ 소스코드 #include int n..
BOJ 15685 · 드래곤 커브
알고리즘 분류 : 시뮬레이션 문제에 주어진 조건 그대로 드래곤 커브를 만들어서 사각형의 개수를 세는 문제다. 드래곤 커브를 만드는 규칙을 파악해야 한다. 드래곤 커브는 최대 10세대까지 있으며, 일정한 규칙에 따라 만들어진다.1. N세대 드래곤 커브를 만든다고 가정하자.2. N-1세대 드래곤 커브를 우선 복사하고, 이것을 시계 방향으로 90도 회전시킨다.3. 회전 시킨 드래곤 커브를 N-1세대 드래곤 커브의 마지막에 이어 붙인다.위 1~3 과정을 10세대까지 반복하면 된다. 쉽게 구현하기 위해서, 드래곤 커브를 좌표 대신 방향을 사용한다.방향은 0(→) 1(↑) 2(←) 3(↓) 이다.첫 출발 방향을 0으로 둔다.이전 세대의 마지막 방향에서 출발 방향까지 거꾸로 탐색하면서, 각 방향에 1을 더하고 이어 ..
BOJ 14500 · 테트로미노
알고리즘 분류 : 브루트 포스 테트로미노를 N*M 종이 맵에 하나 두었을 때, 얻을 수 있는 합의 최대를 구해야 한다. 테트로미노란 정사각형 4개를 이어붙인 도형이다. 문제에 주어진 5개의 테트로미노는 각각 회전, 대칭이 가능하다. 회전, 대칭을 모두 고려하면, 서로 다른 모양의 도형을 총 19가지 만들 수 있다. 19가지의 도형을 모두 만든다.각 도형에서 하나의 사각형을 중심으로 인덱스를 설정한다. (그림 참조)각 도형 중에 하나를 맵에 두고 합을 구한다.가장 큰 합이 정답이다. C++ 소스코드 #include int n, m, ans; int a[500][500]; const int b[19][4][2] = { { {0,0}, {0,1}, {1,0}, {1,1} }, // ㅁ { {0,0}, {0,1..
BOJ 15686 · 치킨 배달
알고리즘 분류 : 브루트 포스 집과 치킨집과의 거리를 각각 구해서 최소의 치킨 거리를 구하는 문제다. 여러 개의 치킨 집에서 M개의 치킨 집을 고른 후, 문제에 주어진 조건대로 치킨 거리를 구해서 답을 찾아야 한다. 입력받을 때, 치킨집(2)의 개수와 집(1)의 개수를 세고, 각 좌표 (X, Y)를 리스트에 저장한다.치킨집의 총 개수를 K개라고 할 때, 재귀 함수를 통해 K개 중 M개를 골라야 한다. 조합 방식으로 고르면 된다.M개의 치킨집을 모두 고르면, 집과 치킨집과의 치킨거리를 구하고, 그중 최솟값을 정답으로 한다. C++ 소스코드 #include #include #include using namespace std; struct pos { int x, y; }; int n, m, ans=1e9; v..