본문 바로가기

Algorithms

 (28)
[Baekjoon]16235.나무 재테크 16235. 나무 재테크 http://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든 www.acmicpc.net 문제에 나와있는 봄, 여름, 가을, 겨울 순서대로 구현하면 되는 문제였다. 역시 특별한 알고리즘을 요구하지 ..
[Baekjoon]3190.뱀 3190.뱀 http://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 로봇청소기문제랑 비슷한 문제인것 같다. 재귀함수를 이용해서 풀어보려고 했지만 while문을 이용한 풀이가 더 직관적이고 이해하기 쉬워..
[Baekjoon]15685.드래곤 커브 15685.드래곤 커브 http://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다. 방향은 0, 1, 2, www.acmicpc.net 드래곤 커브가 그리는 방향의 규칙을 찾아내는 것이 핵심인 문제다. 이런 문제가 나오면 반드시 직접 그려보면서 ..
[Baekjoon]14503.로봇청소기 14503.로봇청소기 http://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 요즘 시뮬레이션 문제를 연습하고 있다. 특별한 알고리즘이 필요없이 문제에 나와있는 조건대로 구현만 하면 된다고..
[Baekjoon]14891.톱니바퀴 14891.톱니바퀴 http://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다. 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다. 톱니바퀴를 회전시키려 www.acmicpc.net 재귀함수를 이용해서 풀었다. 먼저 톱니바퀴 배열을 2차원 배열로 생성하고 제일 먼저 회전시킬 톱니를 회전시킬때 인접..
[Baekjoon]14499.주사위 굴리기 14499.주사위 굴리기 http://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개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마 www.acmicpc.net 주사위를 굴렸을때 상단에 위치한 값을 출력하는 시뮬레이션 문제다. 주사위의 인덱스를 고정시켜놓고 주사위를..
[Baekjoon]17070.파이프 옮기기1 17070.파이프 옮기기1 http://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 www.acmicpc.net 문제를 읽어보니 바로 전에 풀었던 SWEA의 탈주범검거 문제와 비슷하다는 느낌을 받았다. 일단 현재..
[SWEA]1953.탈주범 검거 bfs로 푸는 문제였다. 그런데 파이프가 연결되어 있는 지점으로만 이동이 가능하기 때문에 현재지점에서 상하좌우를 확인하여 연결이 된 지점으로만 탐색을 수행해야한다. 현재 지점의 파이프 번호에 따라서 탐색할 수 있는 방향이 정해져 있다. 예를 들면 현재 지점의 파이프번호가 2번이면 어차피 좌우로는 이동할 수 없기 때문에 상하 방향만 탐색하도록 한다. 이처럼 파이프 번호에 따라 탐색할 방향을 for문 안에서 미리 걸러주었다. 문제를 풀 때 한가지 착각을 했다. y좌표가 + 되는 것이 아래로 이동하는 방향이고 - 되는 것이 위로 이동하는 방향인데 이것을 반대로 생각해서 계속 틀렸다. 방향에 주의하자. private static void bfs() { visited[R][C] = true; q.add(new P..

티스토리툴바