AndroidTeacher

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 설명 문제에서 주어진 것 처럼, 로봇 청소기가 빈공간을 돌아다니며 청소를 한다. 현재 방향을 기준으로 왼쪽 방향부터 탐색을 시작하며, 방향은 0 = 북 / 1 = 동 / 2 = 남 / 3 = 서쪽을 의미한다. 문제에서 주어진 조건과 상황들을 잘 고려하여 코드를 작성해보자. 풀이 과정 먼저 로봇 청소기의 초기 위치는 무조건 0이며 해당 칸을 청소하게 된다. 청소를 한 칸은 2로 변경하여 청소..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 설명 N x M 크기로 구성된 연구소에 바이러스가 퍼졌다. 연구소의 각 칸은 0, 1, 2로 구성되어 있으며 0은 빈 칸, 1은 벽, 2은 바이러스 이다. 바이러스는 벽을 뚫고 확장할 수 없으며 상하좌우에 인접한 빈 칸으로만 확장이 가능하다. 위 그림과 같이 N x M 모양의 연구소(행렬)가 주어지며, 3개의 벽(1)을 세워야 한다. 3개의 벽을 세웠을 때, 안전영역의 크기(0의 개수)의 최댓값을 구하면..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 설명 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위..

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 문제 설명 문제에서 맵이 주어지고 맵의 첫 칸(0, 0)에 주사위를 놓는다. 그리고 주사위를 상, 하, 좌, 우 로 굴리게 되는데 주사위와 바닥에 닿는 면은 맵의 숫자로 복사가 된다. 그리고 주사위를 굴렸을 때 주사위 위쪽면의 숫자를 출력해야 한다. 따라서, 주사위 전개도를 생각하며 풀어야 하는 문제이다. 풀이 과정 이 문제를 풀기..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 설명 뱀 꼬리물기 문제이다. 뱀이 사과를 먹으면 점점 꼬리를 늘려가게 되며 뱀의 머리가 꼬리에 닿거나 벽에 닿으면 끝나는 게임이다. 뱀의 꼬리를 이동시키는 부분을 큐로 구현하는 부분이 핵심이다. 풀이 과정 이 문제는 큐를 이용한 구현 문제로 다음과 같이 접근하였다. ① 먼저 그래프(맵)을 모두 0으로 채워준다. ② 사과 위치는 모두 2로 채워준다. ③ 앞으로 뱀이 차지하고 있는 부분은 1로 채워줄 ..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 설명 문제에서 주어진 2048 게임을 구현하는 문제이다. 평소의 2048 게임과는 다르게 이동시 새 블록이 추가되지는 않으며 5번 움직였을 때 맵 내의 최대값을 출력하면 된다. 풀이 과정 백트래킹을 이용해 모든 경우의 수에 대해 확인을 해야 하는 브루트포스 문제이다. 움직일 수 있는 방향은 동, 서, 남, 북 4가지 이다. 만약, 동쪽으로 움직인다면 모든 행에 대..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 설명 위의 문제의 그림처럼 N * M 의 보드가 주어졌을 때, 빨간색 구슬을 구멍안에 넣는 게임이다. 파란색 구슬이 구멍안에 들어가서도 안되고, 굴리는 횟수가 10번을 넘어가서도 안된다. 여러가지 제약조건들이 많은 까다로운 BFS 문제이다. 풀이 과정 구슬을 굴리게 되면, 벽이나 구멍에 닿을 때 까지 구슬은 계속 굴러간다. 따라서, 방향 하나..

https://programmers.co.kr/learn/courses/30/lessons/81302#fn1 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 문제 설명 대기실 상태가 그래프(배열)로 주어진다. 응시자 간 간격이 맨하튼 거리 ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 설명 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-..

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제 설명 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었..