본문 바로가기

BOJ

 (223)
[BOJ] 16939. 2X2X2 큐브 https://www.acmicpc.net/problem/16939 * 큐브를 회전할 때 같이 바뀌는 인덱스들을 rotateIdx[][] 에 저장해둔다. * 한 번만 회전하는 경우 나올 수 있는 경우의 수가 6개 이고 한 번 회전할 때 바뀌는 인덱스는 8개 이므로 6*8 로 생성했다. *큐브의 현재 상태를 저장하는 것이 중요하다. * rotate()에는 큐브를 회전하고 check()를 통해 회전한 결과가 옳은지 확인한다. * deque를 사용해서 정방향으로 돌릴 때는 뒤에 값을 넣어주고, 역방향으로 돌릴 때는 앞에 값을 넣어준다. deque의 결과는 다시 큐에 넣고, check()에서 결과를 확인한다. #include #include #include #include using namespace std; ..
[BOJ] 16932. 모양 만들기 * dfs를 이용하여 1로 이루어진 그룹을 라벨링한다. (그룹에 몇 개의 1이 있는지 labelCnt[]에 저장한다) * 현재 좌표의 값이 1이고, 상 하 좌 우 인접한 값이 0인 좌표를 중심으로 탐색을 한다. 인접한 좌표에 0이 있다면 이 값을 1로 바꾸고 다른 그룹들과 합쳐질 수 있다. -> 이를 가능하게 하려면, 0인 좌표의 인접한 칸에 다른 그룹이 있어야 한다. * 만약, 0인 좌표가 다른 그룹과 인접해 있다면 (연합 그룹을 형성하는 1의 개수와 현재 그룹의 개수 +1 )의 최대값이 정답이 된다. * 주의해야 할 점은, 0이 같은 그룹으로 이루어진 1들로 둘러싸여져있을 수 있기 때문에 중복으로 더해주는 것을 방지해야 한다. (set에 그룹의 라벨을 넣어주어서 중복으로 세지 않도록 하였다. ) 1 ..
[BOJ] 17822. 원판 돌리기 * rotate에서는 x의 배수인 원판들을 시계/반시계 방향으로 k번 회전한다. * deque를 사용해서 시계방향은 한 원판에서 가장 뒤에 있는 요소를 가장 앞에 삽입한다. (pop_back -> push_front) 반시계방향은 가장 앞에 있는 요소를 가장 뒤에 삽입한다. (pop_front->push_back) * deque에 저장된 값들을 다시 map에 넣는다. * removeNums()에서는 인접한 숫자들을 지운다. 만약, 전체 원판을 통틀어 지울 수가 없다면 평균값에 따라 원판의 값을 조절한다. * 각 좌표에서 상 하 좌 우를 살펴봤을 때 같은 수가 있으면 큐에 넣어준다. 만약, 전체 원판을 봤을 때 큐에 아무런 값도 없다면 지울 값이 없다는 것이다. * *평균값을 double로 구해줘야 한다...
[BOJ] 16918. 봄버맨 * bombTime[] 폭탄이 설치되는 시간을 저장한다. * 처음 1초 동안 봄버맨은 아무것도 하지 않는다. -> n == 1일 때 입력받은 폭탄을 그대로 출력해야 한다. * 1초 동안 폭탄이 없는 곳에 폭탄을 설치한다. (이때 설치하는 폭탄은 first (처음 폭탄이 터지는 시간) + 2 시간에 터진다. ) * 1초 프로세스 도중에 sec == n이 되면 실행을 멈춘다. * 폭탄을 터트린다. (bomb(터질 폭탄 -> 이 시간에 터질 폭탄만 터트린다)) -> 1초 소요 * 폭탄은 터질 때 주변의 폭탄들을 같이 터트리기 때문에 자신과 같은 숫자를 가진 폭탄은 터트리지 않는다. * 주변의 폭탄을 터트린 후에 현재 터져야 할 폭탄들을 터트려준다. (62 ~ 72 line) #include #include u..
[BOJ] 9328. 열쇠 * BFS로 완전 탐색을 한다. * 열쇠 상태를 계속 저장한다. (keystate) * 상근이는 빌딩 밖을 자유럽게 돌아다닐 수 있기 때문에 맵의 바깥쪽은 전부 '.'으로 만들어준다. *(0,0)부터 탐색을 시작한다. - 문을 만나면 지금 가지고 있는 키로 열 수 있는지 확인한다. 열 수 있다면 빈공간('.')으로 만들어준다. - 문서를 만나면 훔칠 수 있는 문서의 개수인 (res)를 1만큼 증가시키고 빈공간('.')으로 만들어준다. - 열쇠를 만나면 keystate를 비트마스킹을 이용하여 값을 변경해주고 빈 공간으로 만들어준다. - 여기서 중요한 것은 열쇠를 만났을 때 지금 까지 방문했던 좌표 중에 이제는 열 수 있는 문이 있을 수도 있기 때문에 visited 배열을 초기화한다. (초기화하는 방법 말고..
[BOJ] 14391. 종이조각 * (0,0) ~ (n-1, m-1) 까지 완전 탐색하면서 백트래킹으로 전수조사를 한다. * 방문 표시 된 좌표는 가로로 숫자를 만드는 부분이고, 방문 표시가 안 된 부분은 세로로 숫자를 만드는 부분이다. T T T T 이렇게 방문표시가 되어있다면 이렇게 방문 표시가 된 부분은 가로로 직사각형을 만들고. 아닌 부분들은 세로로 직사각형을 만든다. * 이어지는 숫자를 string으로 만들어서 sum에 누적합을 해 준다. #include #include #include using namespace std; int n, m; char map[5][5]; int dx[2] = {1, 0}, dy[2] = {0, 1}; bool visited[5][5]; int ans = 0; bool chk[5][5]; int ..
[BOJ] 1600. 말이 되고픈 원숭이 * 최단 거리가 정답이 아닐 수도 있다. * 1 3 5 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 처럼 도착 지점이 장애물로 막혀져있는 경우 0 0 0 x 0 0 0 x 0 1 0 0 0 1 0 x로 표시되어있는 지점까지 원숭이로 이동한 후 말의 이동을 하는 방법이 도착할 수 있는 최선의 방법이다. * 큐에는 4가지 값이 들어간다. {움직인 횟수, 말로 움직인 횟수, 좌표} 말로 움직인 횟수가 k보다 작을때까지만 말로 움직인 좌표를 큐에 넣을 수 있다. 원숭이로 움직인 횟수는 항상 넣는다. (최단 경로 != 정답) *코드가 깔끔하지 않다. *dx / dy => 상하좌우 cdx / cdy => 대각선 #include #include #include #define INF 987654321 usin..
[BOJ] 9470. Strahler 순서 + TC * 위상정렬을 이용 * 큐에서 방문하는 노드로 들어오는 가진 강의 순서가 가장 큰 값을 maxCost[] 에 저장한다. (이 값은 항상 최대값만 저장) * cost[]에는 가장 큰 값을 maxx라고 가정한다면 maxx가 1번 들어오면 maxx값을 그대로 저장하고 2번이상 들어오면 maxx+1 을 저장한다. * maxCost와 cost를 따로 두어야 한다. 같은 배열에 저장한다면 maxCost[] 의 값이 변경되면서 정답이 달라지기 때문이다. 간단하게 예를 든다면 3 4 2 4 1 4 이렇게 간선이 주어져있다고 가정하자. 1,2,3 번 노드는 강/호수 또는 바다와 인접한 노드이므로 1의 값을 가진다. 4번이 Strahler순서가 되는 값을 가질 텐데, indegree[4] = 3이다. 처음 1의 인접리스트..

티스토리툴바