PS
-
백준 1175번 배달PS 2021. 3. 29. 23:52
www.acmicpc.net/problem/1175 중복체크를 위한 상태공간을 정의해야 합니다. 탐색이 발산적으로 이루어지므로 목표지점 1을 방문할 때, 목표지점 2의 경로를 지나갈 수 있습니다. 따라서 이 두 개는 따로 체크되어야 합니다. 그리고 방향은 매시간 달라지므로 어떤 방향으로 나가냐(혹은 들어오냐)에 따라 체크가 따로 되어야 합니다. 따라서 상태공간을 이루는 요소로 좌표, 방향, 1의 방문 여부, 2의 방문 여부 입니다. #include #include #include #include #include #include using namespace std; #define MAX 50+1 struct point { int y, x, dir, cnt; bool cVisited = false, dVis..
-
백준 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..