Code/BOJ
-
#17822 원판 돌리기Code/BOJ 2019. 12. 25. 23:00
문제 요약 및 알고리즘 핵심 1. 원판에 대한 정보가 입력값으로 주어지고 또 명령값 x,d,k에 의해 최종적으로 갱신되어 남아있는 원판의 점수의 합을 출력하는 문제이다. 2. 문제에서 명령값으로 x,d,k값을 주는데 x값은 원판 번호를 뜻하고, d는 해당 원판의 회전방향 (시계 or 반시계), k는 얼만큼 회전시키는지이다. 3. 따라서 해당 조건을 쉽게 만족시킬 수 있도록 자료구조와 알고리즘 설계를 간편하게 해야했다. 원판을 펼쳐 2차원 배열로 표현한 것이 핵심이었다. 그 후 시계 반시계방향 회전을 적용할 수 있었고 k번회전, 평균에 맞춰 원판 값 갱신하기 등 다양한 요구사항을 문제의 요구에 맞춰 구현만 하면 된다. 알고리즘 순서 1. x의 배수에 해당하는 원판을 모두 시계 또는 반시계방향으로 k번 회전..
-
#1520 내리막길Code/BOJ 2019. 12. 19. 20:33
알고리즘 핵심: 백트래킹! 계속 dfs,bfs로 문제를 풀다가 오랜만에 dp를 활용한 백트래킹 방법을 적용하였습니다. DFS를 통해 목적지까지 탐색하였고 탐색을 하면서 방문(visit[x][y]>=0)표시를 해나갔습니다. 그 후 목적지인 오른쪽 하단에 도착하면 1을 리턴하였고 범위를 벗어나는 영역은 0을 리턴하였습니다. 그 외에 방문이 돼 있는 지역이 next x,y로 선정이 되어 재귀함수를 통해 x,y가 된다면 방문이 돼 있는 지역이므로 백트레킹을 적용하여 그떄의 visit[x][y](이전의 visit[nx][ny]값이라고 보면 됨) 를 리턴하였습니다. 그리고재귀를 통해 백트래킹을 적용한 함수 호출하는 부분은 visit[x][y]=visit[x][y]+dfs(nx,ny)이렇게 설정하면 백트래킹을 하면서..
-
#2668 숫자 고르기Code/BOJ 2019. 12. 17. 18:43
알고리즘 핵심은 1부터 n까지 사이클을 형성하는 노드를 찾아가면서 싸이클을 형성하는 노드 갯수만큼 카운트값을 올리고 방문처리가 돼 있는 노드는 스킵하여 출력하는 것이다. 알고리즘 순서 1. 1부터 n까지 반복문 형성 후 다시 1부터 n까지 사이클을 형성하는 노드들을 방문처리해준다. 2. dfs를 통해 처음 입력한 노드가 재귀를 통해 다시 나오게 된다면 true를 리턴하고 재귀를 해준 dfs함수가 역순으로 되돌아가면서 사이클 크기만큼 cnt값을 올려주며 true를 반환한다. 3. 사이클을 형성하지 않을시 언젠가 방문이 돼 있는 노드를 방문하게 되면서 false를 리턴하고 true가 있는 조건문에는 들어갈 수 없게 된다. 그래서 cnt값은 변화가 없고 false를 반환하게 된다. 4. dfs 안에서 2,3 ..
-
#17837 새로운 게임2Code/BOJ 2019. 11. 26. 17:24
재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다. 턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. A번 말이 이동하려는 칸이 흰색인 경우..
-
#2638 치즈Code/BOJ 2019. 11. 26. 17:07
문제를 풀기전에 알고리즘 설계를 다음과 같이 했습니다. 빈칸과 2개 이상 접촉해 있다면 치즈를 녹인다 만일 내부 공기라면 치즈에 영향을 주지 않는다. 알고리즘 순서 1. 초기 외부 공기 설정 bfs 함수의 visit 배열을 전역변수로 설정하여서 방문처리가 돼 있지 않은 visit들로만 참조를 하였습니다. 따라서 매 턴마다 100*100범위 안에서 visit처리가 돼 있지 않은 값들만 고려하게 되어 탐색횟수를 줄일 수 있었습니다. 2. 외부공기와 접촉해 있는 치즈 외부공기로 바꿔주기 3. 내부공기였는데 외부공기와 접촉해 있다면 외부공기로 바꿔준다 2,3 반복