Study hard

www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net [풀이] bfs를 사용하여 풀 수 있는 문제였다. 주변을 탐색할 때 왼쪽 방향부터 시계 반대방향으로 탐색하고, 청소할 수 있는 칸을 찾으면 현재 칸에서의 탐색을 중단해야 한다. 네 방향 모두 청소가 이미 되어있거나 벽인 경우는 네 방향 탐색을 마치고 for문을 빠져나왔을 때 bool flag값을 보고 판단하도록 하였다. #include #include using namespace std; struct Stat..

www.acmicpc.net/problem/12906 12906번: 새로운 하노이 탑 첫째 줄에 막대 A에 놓여져 있는 원판의 개수와 막대 A의 상태, 둘째 줄에 막대 B에 놓여져 있는 원판의 개수와 막대 B의 상태, 셋째 줄에 막대 C에 놓여져 있는 원판의 개수와 막대 C의 상태가 주 www.acmicpc.net [풀이] bfs를 어떻게 써야하는 지 감이 안잡혀서 다른 분의 풀이를 봤다. 각각 막대를 문자열로 받고, 모든 경우에 대해서 bfs를 하는 거였다. 모든 경우 1. 막대A에 원판이 한개 이상 있을 때, 막대B에 원판을 하나 주는 경우, 막대C에 원판을 하나 주는 경우 2. 막대B에 원판이 한개 이상 있을 때, 막대A에 원판을 하나 주는 경우, 막대C에 원판을 하나 주는 경우 3. 막대C에 원판..

www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net [풀이] 문제 풀이에 대한 감을 못 잡아서 결국 다른 분의 풀이를 참고했다. &연산을 사용하여 벽의 유무를 알아내야 하는 문제였다. Map[i][j] & 1 = 0001이면 (i,j)칸의 서쪽에 벽이 있다는 뜻이다. 마찬가지로, Map[i][j] & 2 = 0010이면 북쪽에 벽이, Map[i][j] & 4 = 0100이면 동쪽에 벽이, Map[i][j] & 8 = 1000이면 남쪽에 벽이 있다는 뜻이다...

www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net [풀이] dfs 조합과 bfs flood fill을 사용하여 풀었다. dfs를 사용하여 M개의 바이러스 위치의 조합을 구하고, 각 조합마다 bfs를 사용하여 바이러스가 연구소 전체에 퍼지는 시간을 구하였다. bfs를 호출할 때마다 visited배열을 초기화하고, bfs가 끝나면 최소시간을 갱신해야한다. #include #include #include #include //memset using namespace std; ..

www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net [풀이] bfs를 사용하여 풀었다. 말처럼 이동한 횟수가 K번 미만이면 말처럼 이동한 칸을 queue에 넣는다. 그리고 원숭이로 이동하는 경우 또한 queue에 넣어야한다. #include #include using namespace std; struct Monkey { int x, y; int horse;//말 방식으로 이동한 횟수 int dist;//해당 칸까지 이동한 횟수 }; int K,..

www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net [풀이] bfs를 사용하여 풀었다. 각 벽마다 주변에 있는 0의 개수를 세도록 하면 visited[1001][1001]배열을 매번 false로 초기화 해줘야 하기 때문에 시간 초과가 난다. ※방문하지 않은 0마다 bfs를 호출하여 연결된 0의 개수를 센 다음, 탐색하면서 만난 벽들에 그 개수를 더해주도록 하였다. #include #include #include //scanf #include..