백준
15683_감시
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 먼저 cctv가 5개가 있는데 해당 cctv들의 각 방향마다 체크할 방향들을 세트로 묶어두었다. 예를 2번 cctv라면 [ [[0,1],[0,-1]] , [[1,0],[-1,0]] ] 위와같이 총 2개의 방향을 가지고 각각 상하나 좌우를 보게 된다. 이렇게 cctv 번호마다 방향을 정해주고 cctv가 몇개있는지 세주고, dfs를 사용해서 모든 경우를 체크했다. 위에서부터 내려가면서 각 ..
14891_톱니바퀴
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 결국 중요한건 1~4번째까지의 수레를 돌리느냐 안돌리냐를 결정해주면 된다. 그래서 0으로 구성된 visited배열을 [0,0,0,0] 으로 잡은 후에 한 프로세스를 거치고 [0,0,1,-1]와 같은 배열을 얻을 수 있다면 단순히 이 배열을 순회하면서 회전만 시키면 된다고 생각했다. 즉, 회전과 검사를동시에 하지말고 2단계에 나눠서 한다고 생각하면 된다. 여러 방법이 있겠지만 회전을 시작하는 톱..
14890_경사로
https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 우선 문제를 쪼개서 가로줄만 확인할 수 있게 생각해보았다. 세로줄은 결국 회전시키면 가로줄과 같기 때문에 두번 탐색하면 될거라 생각했다. 문제 케이스에서 3 2 2 1 1 1 해당 라인을 가로줄이라 생각해고 생각해보자. while문을 하나 돌리며 idx 값을 n까지 탐색하면 된다. 1. 만약 idx 가 가리키는 값과 다음 값의 차이가 1이 넘어가면 그즉시 종료한다. 2. 만약 다음 숫자가 idx가 가리키는 값보다 작다면..
14503_로봇청소기
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 기본적으론 재귀함수의 형태를 띠지만 무작정 dfs로 구현하기에는 조금 무리가 있다. 현재 위치를 청소한다. 현재 위치에서 다음을 반복하면서 인접한 칸을 탐색한다. 현재 위치의 바로 왼쪽에 아직 청소하지 않은 빈 공간이 존재한다면, 왼쪽 방향으로 회전한 다음 한 칸을 전진하고 1번으로 돌아간다. 그렇지 않을 경우, 왼쪽 방향으로 회전한다. 이때, 왼쪽은 현재 바라보는 방향을 기준으로 한다. 1번으..
14502_연구소
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 벽을 세운 후에 미로를 풀면 된다. 바이러스를 퍼뜨리는것을 함수로 만들어서 dfs로 구현하였다. 그후 바이러스가 있다면 주위로 퍼져나가게끔 2차원 배열 전체에서 dfs를 한번씩 실행한 후에, 나온 보드에서 0의 개수를 세주며 업데이트를 해준다. 벽을 3개 세워줘야 하는데, 중요한건 꼭 3개가 채워져야 한다는 것 즉, 전체 배열 중에서 3개를 순열로 뽑아내서 m으로 나눈후 몫을 x좌표, 나머지를 y좌표로 삼아 ..
14499_주사위굴리기
https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 문제를 처음보면 주사위의 전개도가 그려지는데, 이를 활용해서 풀었다. 먼저 전개도의 가로,세로를 저장해주었다. 2 4 1 3 5 6 문제처럼 위와같은 전개도가 있다면 4,1,3 2,1,5,6 을 큐로 저장해주었다. 두 배열을 dice_r,dice_c라고 생각해보자. 만약 위,아래로 움직인다면 단순히 2,1,5,6 의 앞이나 뒤를 떼..