본문 바로가기

백트래킹4

[BOJ] 17825 : 주사위 윷놀이 문제 링크 17825번: 주사위 윷놀이 (acmicpc.net) 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 주사위로 진행되는 윷놀이를 규칙대로 구현하는 문제. 풀이 왼쪽과 같은 윷놀이 판을 어떻게 구현할지가 일단 첫번째 문제였다. 파란색 칸을 밟았을 때 경로가 바뀌는 것을 어떻게 표현해야하지 생각하다가, 처음엔 10, 20, 30 칸을 밟을때마다 경로가 바뀌니까 4가지 경우의 경로를 따로 만들려고 했었다. 하지만 그렇게하면 이동할 칸에 이미 말이있는지 파악하기가 힘들었다. 그래서 나는 내 임의대로 각 칸마.. 2022. 5. 19.

[BOJ] 17142 : 연구소 3 문제 링크 17142번: 연구소 3 (acmicpc.net) 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 연구소 모든 칸에 바이러스를 퍼트리는데 걸리는 시간을 구하는 BFS 문제. 풀이 연구실을 N X N 크기의 칸으로 표현했을 때 각 칸은 0 빈 칸, 1 벽, 2 바이러스 중에 하나로 채워진다. 바이러스에는 활성 바이러스와 비활성 바이러스가 있다. 둘다 바이러스지만 활성 바이러스는 전염성을 가지고 비활성 바이러스는 전염성이 없다. 하지만 활성 바이러스가 비활성 바이러스와 만나면 활성화시킬 수 있다. 2 ~ 10개 .. 2022. 5. 17.

[BOJ] 9874 : Wormholes 문제 링크 9874번: Wormholes (acmicpc.net) 9874번: Wormholes Farmer John's hobby of conducting high-energy physics experiments on weekends has backfired, causing N wormholes (2 2022. 4. 22.

[BOJ] 15684 : 사다리 조작 문제 링크 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 백트래킹으로 완전탐색하기. 풀이 기존의 사다리에 3개 이하의 새로운 다리를 놓아서 i번 사다리값이 i가 나오도록 만드는 문제. 백트래킹을 통해서 새로 다리를 놓을 위치를 정한다. 여기서 다리의 여부는 is_connected 배열을 이용해서 저장했다. is_connected[높이][막대 번호1][막대 번호2] 이렇게 3차원배열로 만들어주었고 값이 true면 1번 2번 막대 사이에 가로로.. 2022. 4. 14.

이전 1 다음

티스토리툴바