목록전체 글 (124)
풀이 보관함
🔗문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 🖍풀이 std::queue water; std::queue S; std::pair D; // 비버의 소굴은 이동하지 않는다. 입력을 받으면서 필요한 좌표들을 미리 저장한다. 필요한 좌표를 찾기 위해 이차원 함수를 탐색하고 싶지 않기 때문이다. 이동이 필요한 물과 도치를 BFS 탐색을 위해 queue에 저장한다. void BFS(std::queue& q, const bool isWater, bool& f..
🔗문제 16397번: 탈출 16397번: 탈출 첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다. 각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 www.acmicpc.net 🖍풀이 문제의 조건들만 잘 유의하면 바로 풀 수 있다. 어떤 경로를 통해서 값이 나왔는지 알고 싶어서 구조체를 이용해 풀었다. struct pair { public: std::string str; int num; pair(int _num, std::string _str) :num(_num), str(_str){}; }; str: 경로 num: 번호 BFS를 이용해 풀었기 때문에 G..
🔗문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 🖍풀이 내 기준 너무 너무 어려웠다. 결국 풀다가 검색의 힘을 빌렸고 참고하기 좋은 글을 첨부한다. 🔗 글 읽기 - ★☆★☆★ [필독] 벽 부수고 이동하기 FAQ ★☆★☆★ 글 읽기 - ★☆★☆★ [필독] 벽 부수고 이동하기 FAQ ★☆★☆★ 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net MAX 1,000인데 실수로 10,000으로 설정해서 틀렸..
🔗문제 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 🖍풀이 불 좌표, 상근이 좌표를 저장할 두 개의 queue를 생성하고 입력 받을 때 push해준다. std::queue fire; std::queue me; 재방문 방지 배열도 만들어 주었다. int visited[MAX][MAX]; 가장 중요한 BFS 탐색 방법 불 이동이랑 상근이 이동의 탐색에 겹치는 코드가 많아서 함수로 해결했다. void BFS(std::queue& q, const bool is..
> 연산자 (Shift) 비트를 n 만큼 왼쪽 혹은 오른쪽으로 이동시킨다. int n1 = 9; // (2진수 배열로 나열하면) 01001 int n2 = 11; // (2진수 배열로 나열하면) 01011 int n3 = n1 2 = 00010 = 2; int n3 = 28 > 2 = 00111 = 7; + 이때, shift 연산자는 곱셈, 나눗셈과 관련이 있다. 왼쪽으로 1칸 이동할때마다 정수의 값은 2배 로 커지고 (곱셈과 관련) 오른쪽으로 1칸 이동할때마다 정수의 값은 1/2배 가 된다. (나눗셈과 관련) 예제로 4/2 = 4>>1 과 동일한데, CPU 입장에서는 곱셈,나눗셈보다 비트 연산이 부담이 적어 성능 향상에도 도움이 된다. [출처] [c++] 비트 연산|작성자 YEON
🔍문제 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 📝 풀이 자릿수의 변화에 당황하지 않는다면 쉽게 풀 수 있다! 자릿수가 변화에 맞는 식을 아래와 같이 세워줍니다. D = num * 2 % 10000; S = (num == 0 ? 9999 : num-1); L = num % 1000 * 10 + num / 1000; R = num % 10 * 1000 + num / 10; 전형적인 queue를 이용한 BFS로 풀되, comma..
문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 입력을 열, 행으로 받기 때문에 문제를 꼼꼼히 읽지 않으면 틀리기 쉽다. 입력받을 때 익은 토마토가 있는 좌표를 queue에 입력한다. 0, 0부터 익은 토마토를 BFS 탐색해버리면 익은 토마토가 여러 개 있을 때, 중복 방문할 가능성이 있다. BFS로 익지 않은 토마토가 있는 곳을 탐색한다. 이 때, queue에서 꺼낸 좌표의 토마토의 최소 일수 + 1 해준다. 결과를..
문제 https://www.acmicpc.net/problem/6593 3차원 개념을 활용해서 푸는거라 문제 이해가 처음에는 좀 어려웠지만 문제는 쉬운 편. 풀이 입력을 받을 때, S와 E의 좌표를 저장해준다. 시작 좌표는 탐색 시작을 위해 사용한다. 목표 좌표는 출력에 사용한다. 이번 문제는 2차원 배열에서 ‘면'의 개념을 추가한 3차원으로 탐색을 해야 한다. int dx[6] = {1, -1, 0, 0, 0, 0}; int dy[6] = {0, 0, -1, 1, 0, 0}; int dz[6] = {0, 0, 0, 0, 1, -1}; 최소 이동 거리 저장 및 재방문 확인을 위한 배열을 만들어 주었다. #define MAX 31 int visited[MAX][MAX][MAX]; // 최소 이동 거리 각 ..
문제 https://www.acmicpc.net/problem/10026 풀이 BFS로 풀었다. 비장애인과 적록색약의 탐색 함수를 2개 만들어서 풀었다. 다른 방법으로는 입력 배열을 2개 만드는 방법이 있다. R or G 은 1로 저장 B는 0으로 저장 이렇게 R과 G를 같은 걸로 취급하면 함수를 1개만 짜도 된다는 장점이 있다. 소스 HTML 삽입 미리보기할 수 없는 소스