전체 글
-
백준 9328번 열쇠PS 2021. 3. 29. 23:45
www.acmicpc.net/problem/9328 탐색이 1번으로 끝나지 않습니다. 탐색 도중 열쇠를 얻게 되면 탐색할 수 있는 공간이 늘어나기 때문이죠. 따라서 더 이상 열쇠를 얻지 않을때까지 탐색을 반복해주면 됩니다. #include #include #include #include #include using namespace std; #define MAX 1005 struct point { int y, x; }; int test; int n, m, res; char map[MAX][MAX]; bool visit[MAX][MAX]; string key; int dy[] = { 1, -1, 0, 0 }; int dx[] = { 0, 0, 1, -1 }; void print_map() { for (int..
-
백준 16952번 체스판 여행PS 2021. 3. 29. 23:40
www.acmicpc.net/problem/16952 방문체크를 하기 위해 상태공간을 정의할 필요가 있다. 상태공간에 들어갈 요소로 좌표, 현재 번호, 말의 종류가 있겠다. 문제에서 요구하는 값은 시간과 바꿈수이다. 이 둘 모두가 최소로 나와야 하므로 두 개가 비교해줄 필요가 있다. 이를 위해 pair를 사용했다. #include #include #include #include #include using namespace std; #define MAX 10 + 1 struct point { int y, x; int kind, num; int time, change; }; int n, sy, sx; int map[MAX][MAX]; pair visited[MAX][MAX][150][3]; int dy[] ..
-
백준 16920번 확장 게임PS 2021. 3. 29. 23:31
www.acmicpc.net/problem/16920 범위 크기만큼 bfs를 돌리면 확장 1번이 진행된다. 모든 플레이어에게 개인 큐를 지급해서 범위만큼 돌리도록 한다. #include #include #include using namespace std; #define MAX 1000 + 1 struct point { int y, x; }; int n, m, pCnt; bool endCondition; int map[MAX][MAX]; int range[10]; int res[10] = {0, }; int dy[] = { 1, -1, 0, 0 }; int dx[] = { 0, 0, 1, -1 }; queue q[10]; void printMap() { for (int i = 0; i < n; i++) {..
-
백준 8111번 0과1PS 2021. 3. 29. 23:26
www.acmicpc.net/problem/8111 1. 1부터 시작하여 뒤에 1, 0을 달아주며 완전탐색을 한다. - 탐색 시, 오버플로우가 나지 않도록 (현재 숫자 % 목표 숫자)를 넣어주도록 한다. - 탐색 종료 후, 만든 숫자를 출력해야하므로 트리를 만들면서 탐색한다. 2. 탐색 종료 후, 트리를 바텀에서부터 탑으로 향하며 만든 숫자를 출력한다. #include #include #include #include #include #include using namespace std; #define MAX 20000 + 1 int test; int n; int parent[MAX]; char s[MAX]; void bfs() { queue q; bool visit[MAX]; memset(visit, fa..
-
백준 1062번 가르침PS 2021. 2. 1. 21:06
www.acmicpc.net/problem/1062 백트래킹으로 풀 수 있는 문제이다. 가르칠 단어를 정하고 가르칠 수 있는지에 대한 여부를 확인할 때, 비트마스킹을 이용해 단어를 int형 변수에 저장하면 시간최적화가 가능하다. #include #include #include using namespace std; #define MAX 50 int n, k; bool visit[27]; int res; string S[MAX+1]; void input() { cin >> n >> k; for (int i = 0; i > S[i]; } } int check_same() { int cnt = 0; for (int i = 0; i < n; i++) { int len = S[i].l..
-
백준 4577번 소코반PS 2021. 1. 29. 00:56
www.acmicpc.net/problem/4577 이동연산을 구현할때, b. B. w. W를 그대로 사용했으면 구현이 복잡해졌을 것이다. 문제를 분해하여 단순하게 생각하기 상태를 복사시켜서 저장해놓기 #include #include #include #include using namespace std; struct point { int y, x; }; int py, px; int n, m; char tmap[17][17]; char map[17][17]; int dy[] = { -1, 1, 0, 0 }; int dx[] = { 0, 0, -1, 1 }; int Dir[51]; string tDir; vector target; void print_map() { cout > n >> m; if (n == 0..
-
백준 20061번 모노미도미노2PS 2021. 1. 28. 00:30
www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 초록색 보드와 파란색 보드에 쓰이는 연산을 거의 동일한 코드로 구현할 수 있습니다. 다만 사고실험이 조금 복잡했던 문제였습니다. 정교한 사고실험과 설계-구현의 검증이 부족함을 느꼈습니다. #include #include using namespace std; int green[7][5]; int blue[7][5]; int n, t, sy, sx; int score_line, score_line_cnt..
-
백준 16929번 Two DotsPS 2020. 4. 14. 23:06
https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다. www.acmicpc.net 정점의 갯수가 4이상인 사이클의 존재 여부를 묻는 문제입니다. dfs를 돌면서 이미 방문한 지점도 확인해주어야 하는 문제였습니다. #include #include #include using namespace std; struct point { int y, x; }; int n, m; char map[51][51]; bool visit[51][51]; bool suc; in..