C++ 검색 결과
55 개의 검색 결과가 있습니다.
코딩/백준 (C++)

백준 5213번: 과외맨 (C++)

접근 https://www.acmicpc.net/problem/5213 5213번: 과외맨 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 500) 다음 줄부터 N*N-N/2줄(/는 정수 나눗셈이다)에는 두 양의 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ 6, 1 ≤ i ≤ N * N - N / 2) 타일 i의 왼쪽에 쓰여 있는 숫자는 Ai, 오른 www.acmicpc.net path 배열에 n번 블록에 도달했을 때 이전 경로의 블럭 번호를 저장해줌으로써 경로를 쉽게 저장해 줄 수 있다. bfs 알고리즘을 이용하여 최단거리 이동을 계산하면서, 일반적인 MAP에 그리는 상하좌우 대신 6방향으로 연결되었는지를 판단해주는 함수를 이용하여 문제를 해결할 수 있다. 6방향으로 이동하는 기준을 잘 정해주고 나면 ..

2022. 5. 7. 19:22
코딩/백준 (C++)

백준 12886: 돌 그룹 (C++)

접근 https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 처음에는 DFS나 BFS를 이용하고, set을 이용해 중복되지 않도록 A, B, C를 저장하고 탐색하였지만 짐작대로 시간초과되었다. 시간을 단축할 수 있는 방법으로 두가지를 적용하여 문제를 해결할 수 있었다. 숫자를 저장하는데 있어서 3개의 숫자를 set으로 저장하지 않고 두개만 저장하였다. 숫자 두개만 저장하여도 나머지 한개는 세 숫자의 sum - A - B로 결정할 수 있다. set..

2022. 5. 7. 16:09
코딩/백준 (C++)

백준 3108번: 로고 (C++)

접근 https://www.acmicpc.net/problem/3108 3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net 처음에 문제를 볼 때부터 사각형끼리 연결될 경우 유니언하는 disjoint set(union-find) 방식 문제 풀이가 떠올랐다. 중간에 생각해보니 배열을 이용하여 사각형을 실제로 그리고 bfs를 통해 따로 떨어진 묶음들을 카운트하는 방법이 더 간단한 방법이었음을 깨달았지만 이미 너무 많이 지나쳐와서 disjoint set 알고리즘을 이용하여 문제 풀이 완료하였다. 두개의 사각형이 연결되는 방식은 매우..

2022. 5. 6. 01:49
코딩/백준 (C++)

백준 2186번: 문자판 (C++)

접근 https://www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 처음에는 DFS 알고리즘을 이용하여 K칸 이동하는 식을 통해 문제를 해결하려 하였지만, 딱 봐도 시간초과일 것 같아 중복 계산을 막을 수 있는 방법을 찾기 시작하였다. 결과적으로는 DP[101][101][81]의 배열을 만들어 DP를 이용하여 풀 수 있었다. DP[a][b][c] = d 라고 할 때 이 의미는 MAP[a][b]에 있는 문자가 c번째로 쓰일..

2022. 5. 5. 21:55
코딩/백준 (C++)

백준 16946번: 벽 부수고 이동하기 4 (C++)

접근 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 입력을 받고 MAP을 순회하면서 0이 아닌 지점들에서 bfs 탐색을 진행한다. 인접한 0의 갯수를 카운트하면서 동시에 또다른 큐를 만들어 인접한 1들을 체크해주고 bfs 탐색이 완료되면 인접접한 1들(벽들)에 카운트한 숫자를 더해준다. 마지막으로 다시 MAP을 순회하면서 10으로 나누어 남는 나머지를 출력해준다. 코드 #include #include #include us..

2022. 5. 5. 16:41
코딩/백준 (C++)

백준 16954번: 움직이는 미로 탈출

접근 https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 체스판의 크기가 8이므로, 벽이 총 8회 움직이고 나면 체스판에 벽이 사라지게 된다. 즉, 욱제가 8턴까지 벽에 맞지 않고 살아있다면 체스판을 탈출할 수 있다고 생각하고 dfs 알고리즘을 이용하여 풀이하였다. 추가적으로 벽의 좌표를 구조체로 만들어 총 8개의 배열에 저장(벽이 총 7번 이동할 때까지 욱제가 살아있으면 체스판 탈출 가능)해주었고, 욱제가 이동할때 해당하는 벽의 위치에..

2022. 5. 5. 13:12
반응형