반갑습니다!

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 문제를 보고 BFS라고 생각하기 쉽지만, 백트래킹을 통한 완전탐색 문제이다. 이 문제는 크게 2가지 부분으로 구성된다. i번째 사람이 어느 계단으로 갈지 결정하는 부분 구현 계단을 모두 빠져나가는 부분 구현 1번의 경우 백트래킹을 통해 어렵지 않게 모든 경우를 구할 수 있다. 그렇다면 이제는 2번을 구현해야한다. 어느 계단으로 갈 지 결정했다면, 1번 계단으로 가는 사람들이 계단까지 걸리는 시간과 2번 계단으로 가는 사람들이 계단까지 걸리는 시간을 구할 수 있다. 이를 계산한 뒤, 걸리는 시간을 오름차순으로 정렬한다. 그리고 계단을 queue로 구현하여 계단..

14503번: 로봇 청소기 www.acmicpc.net 풀이 문제에서 주어진대로 구현하면 되는 시뮬레이션 문제이다. 로봇이 탐색하는 부분을 구현하는 것이 핵심이다. 코드 #include using namespace std; int r, c, rx, ry, rd; int map[50][50]; const int dx[] = { 0, 1, 0, -1 }, dy[] = { -1, 0, 1, 0 }; int simulation() { // 청소한 바닥의 개수 int cnt = 0; while (true) { int x = rx; int y = ry; // 현재 위치의 바닥 청소 if (map[y][x] == 0) { map[y][x] = 2; cnt++; } bool wash = false; // 현재 방향의 ..

1194번: 달이 차오른다, 가자. www.acmicpc.net 풀이 이 문제에서는 열쇠를 보유하고 있는 상태를 표시하는 것이 관건인 문제이다. 열쇠 보유 상태를 표현하기 쉽게 하기 위해서 비트 마스킹을 사용했다. a 열쇠를 집은 경우 000001 으로 표기한다. b 열쇠를 집은 경우 000010 으로 표기한다. c 열쇠를 집은 경우 000100 으로 표기한다. d 열쇠를 집은 경우 001000 으로 표기한다. e 열쇠를 집은 경우 010000 으로 표기한다. f 열쇠를 집은 경우 100000 으로 표기한다. 비트 마스킹을 사용하면 여러개의 키를 가지고 있는 경우도 쉽게 표현할 수 있다. 그리고 열쇠를 가지고 있는 경우에 따라서 갈 수 있는 경로가 달라지기 때문에 중복 체크하는 배열을 3차원으로 구성해서..

16986번: 인싸들의 가위바위보 www.acmicpc.net 풀이 가위바위보 손동작 수가 N이라면 지우는 [1, 2, 3, ... , N] 을 낼 수 있다. 따라서 지우가 낼 손동작의 순서를 모두 구해서 확인해보면 해결할 수 있다. 코드 #include #include #include using namespace std; int n, k; int a[10][10]; int jw[10], kh[20], mh[20]; bool simulation() { int jw_idx = 0, kh_idx = 0, mh_idx = 0; int jw_win = 0, kh_win = 0, mh_win = 0; // 다음 차례에 가위바위보 할 사람을 가리키는 변수 // 0: 지우, 1: 경희, 2: 민호 int rest =..

14502번: 연구소 www.acmicpc.net 풀이 DFS와 BFS를 활용해서 해결하였다. 백트래킹으로 모든 경우의 벽을 세워보고, 벽을 3개 세웠을 경우에 BFS를 통해 빈 칸의 최대 넓이를 구하면 된다. 코드 #include #include #include #include using namespace std; int n, m, blank, ans; int map[8][8]; vector virus; vector blanks; const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 }; int bfs(int count) { bool visited[8][8] = { false, }; queue q; // 큐에 바이러스를 모두 넣는다 for (auto v : ..