Python/백준
15685_드래곤 커브
https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 조금 색다른 유형이었는데 푸는 과정이 재밌었던 문제였던 것 같다. 우선 결국 지도에 드래곤 커브들을 그려야 하는게 목표였던것 같다. 그래서 우선은 회전하는 방법에 대해서 생각을 해보았다. 어떤 좌표에서 특정좌표로 회전시키든, 0,0에서 회전시킨다고 생각 하고 다시 옮기면 회전시킨 좌표를 알 수 있다. 그런데 좌표의 회전은 결국, x,y좌표를 바꾸고 시계방향이라면 뒤에값에..
15684_사다리조작
https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 생각보다 되게 까다로운 문제였다... 2차원 배열을 하나 잡는데 이는 각 사다리간 사이에 사다리가 놓여져 있는지, 비어져 있는지를 나타낸다. 예를들어 위와같이 3개 사다리중에 2개만 연결되어 있다면 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 와같은 배열을 나타낸다. 이때 아래를 제외하고 0으로 감싸주면서 만드는 이유는 그래야 나중에 사다리를 놓을지 안놓을지 검사할때 index에러에..
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번으..