🔗문제 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..

🔍문제 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 삽입 미리보기할 수 없는 소스

문제 https://www.acmicpc.net/problem/5014 풀이 queue를 이용한 BFS로 풀어주었다. ❎ 오답 과정 66%에서 틀렸습니다. 를 11번이나 봤는데 범위 체크가 원인이었다. #define MAX 1000000 bool isVaild(long long a) { if( a > MAX || a > F || a HTML 삽입 미리보기할 수 없는 소스

문제 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 과정 싸이클이 형성되면 팀이 생성된다. 싸이클이 형성되는 경우 1) 첫번째 노드와 마지막 노드가 같을 경우 4 - 7 - 6 - 4 2) n번째 노드와 미지막 노드가 같을 경우 2 - 1 - 3 - 3 🚩 반드시 알아야 할 것 재방문으로 사이클 형성을 알 수 있다. 재방문 노드 이전의 노드들 (경로)은 사이클 형성 불가한 노드라는게 판정된다. 첫번째 노드를 1, 2, 3 .. 로 진행하다가 ..

문제 https://www.acmicpc.net/problem/7562 풀이 방문한 순서대로 좌표를 저장하기 위한 데이터 타입으로 pair를 가지는 queue를 선언했다. std::queue q; 🔍 knight() 처음 함수를 실행하면 (0, 0)에서 방문할 수 있는 위치들를 탐색하여 목표 지점에 왔는지 확인한다. 첫번째 이동으로 갈 수 있는 모든 위치를 queue에 저장한다. 이 때, 재방문 방지를 위해 min[x][y] == 0 이라는 조건을 달아주었다. (한번도 방문 안한 곳이라면 queue에 넣는다.) queue에는 다음 이동으로 갈 수 있는 모든 위치를 갖게 된다. 이 과정을 (N, M)까지 반복한다. (N, M)에 도달하면 바로 return 하기 때문에 최소 이동 횟수을 바로 알 수 있다. ..