본문 바로가기

문제풀기이야기

(19)
14502번_연구소_BOJ 문제 링크14502번 연구소 : https://www.acmicpc.net/problem/14502 문제 설명 및 해결 아이디어3개의 벽을 세워 바이러스가 퍼질 수 없는 안전영역 크기의 최대값을 출력하는 문제이다. 기본 아이디어는 완점탐색을 하면서 바이러스가 퍼질수 있는 영역의 최소값을 구하는 것이다.3개의 벽을 세울 수 있는 모든 경우의 수를 돌린다. 각 경우마다 Depth-First Search(DFS)를 수행하여 퍼질 수 있는 영역의 크기를 계산해나간다.바이러스가 퍼질 수 있는 영역 크기의 최소값을 찾은 후, 전체 크기에서 벽(1)의 개수, 새로 세운 벽 3개, 바이러스 퍼진 영역 크기의 최소값을 빼주면 된다. 코드12345678910111213141516171819202122232425262728..
14503번_로봇 청소기_BOJ 문제 링크14503번 주사위 굴리기 : https://www.acmicpc.net/problem/14503 문제 설명 및 해결 아이디어로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 출력하는 문제이다. 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 한다.A. 현재 위치를 청소한다.B. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행한다.a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한칸을 전진하고 A번부터 진행한다.b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 B번으로 돌아간다.c-1. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 B번으로 돌아간다.c-2. 네 방향 ..
14499번_주사위굴리기_BOJ 문제 링크1449번 주사위 굴리기 : https://www.acmicpc.net/problem/14499 문제 설명 및 해결 아이디어주사위를 굴리면서 주사위의 윗면에 있는 수를 출력하는 문제이다. 주사위를 굴려 해당 칸의 수가 0이면, 주사위 바닥 면에 있는 수가 칸으로 복사된다.해당 칸의 수가 0이 아니면, 칸의 수가 주사위 바닥 면으로 복사된다. 그리고 칸의 수는 0으로 갱신된다. 1, 2, 3, 4로 주어진 명령은 각 동쪽, 서쪽, 북쪽, 남쪽으로 주사위를 굴리는 것을 의미한다.주사위가 굴러가는 것은 네 방향 탐색을 이용했다.12int dx[] = {0, 0, -1, 1 };int dy[] = {1, -1, 0, 0 };cs 주사위가 특정 방향으로 굴러가게 되면, 양 옆면은 그대로 이고 나머지 네 ..