본문 바로가기

■ 알고리즘 문제 풀이/BOJ

 (48)
[BOJ] 백준 16928. 뱀과 사다리 게임 ▶문제설명[BOJ] 백준 16928. 뱀과 사다리 게임 https://www.acmicpc.net/problem/16928 ▶HintBFS & DP 문제이다. 현재 위치와 주사위 던진 횟수를 관리하는 구조체를 만든다. 사다리나 뱀을 만났을 때는 주사위를 던지지 않고 바로 정해진 위치로 이동하게 되며, 사다리나 뱀이 없는 위치에서는 1부터 6까지 주사위를 던지는 모든 경우에 대하여, 적절한 조건을 만족하는 경우에 한해서, 주사위를 던져서 이동한 다음 위치와, 주사위 던진 횟수를 1 증가시켜 큐에 push한다. 1. int visited[101] 배열을 만들고 큰 값으로 초기화해둔다. (visited[위치] = 1에서부터 해당 위치로 가기 위해 주사위를 던진 횟수 중 최소값) 2. BFS 시작 전에 큐에 현..
[BOJ] 백준 6087. 레이저 통신 ▶문제설명[BOJ] 백준 6087. 레이저 통신 https://www.acmicpc.net/problem/6087 ▶HintBFS & DP 문제이다. 각 좌표에서 꺾인 횟수의 최소값을 저장할 2차원 배열을 만들고, 좌표, 이전 방향, 꺾인 횟수에 대한 정보를 관리할 구조체를 하나 만들어서 BFS를 수행하면 된다. 1. 처음에 상/우/하/좌 네 방향에 대하여, 시작점 좌표와 꺾인 횟수 0으로 큐에 push한다. 2. 시작점 좌표의 꺾인 횟수 최소 값을 0으로 한다. 3. 다음 이동할 방향이 그대로이거나 반대 방향인 경우 꺾인 횟수는 그대로 넘겨주고, 다음 이동할 방향이 90도로 꺾인 경우 꺾인 횟수를 1 증가시켜 큐에 push하며 BFS를 수행한다. 큐에 push하는 조건이 중요한데, 다음에 위치할 좌표에..
[BOJ] 백준 14502. 연구소 ▶문제설명[BOJ] 14502. 연구소 https://www.acmicpc.net/problem/14502 ▶Hint브루트포스 & BFS 문제이다. 벽(1)을 3개 놓는 모든 경우에 대하여 바이러스를 최대한 확산시켜본다. 각 경우에 대하여 안전 영역의 크기를 구하고, 가장 큰 값을 답으로 출력하면 된다. 1. 입력을 받으면서 1의 개수를 카운트한다. 2. 벽(1)을 3개 놓는 모든 경우에 대하여 3~4를 수행 3. 바이러스를 최대한 확산 시키면서 바이러스의 개수를 카운트한다. 4. N*M (맵의 전체 크기) - 1의 개수 - 바이러스의 개수 - 3 (벽을 무조건 3개 놓으므로) = 안전영역의 크기 5. 2~4 과정에서 최대값을 구해 답으로 출력한다. ▶Solution
[BOJ] 백준 14500. 테트로미노 ▶문제설명[BOJ] 14500. 테트로미노 https://www.acmicpc.net/problem/14500 ▶Hint브루트 포스 문제이다. 5 종류의 테트로미노를 회전/대칭 시키는 것이 가능하다는 조건이 관건이다. 테트로미노 각각에 초점을 맞추면 문제가 복잡해질 수 있으나, 숫자 판 자체에 초점을 맞추면 문제가 단순해질 수 있다. 입력으로 주어진 숫자 판 자체를 회전/대칭 시키면 테트로미노의 종류 별로 고민할 필요 없이 같은 결과를 얻을 수 있다. (숫자 판을 회전/대칭시켜 8개의 숫자판을 만들 수 있다.) 숫자 판을 90도 회전시키고 나면 행과 열이 바뀌므로 N과 M을 스왑해야한다는 점도 잊어선 안된다. 1. 숫자 판을 회전시켜 4개의 회전된 숫자 판을 만든다. 2. 각 숫자 판에 대해 5 종류의 ..
[BOJ] 백준 14501. 퇴사 ▶문제설명[BOJ] 14501. 퇴사 https://www.acmicpc.net/problem/14501 ▶HintDFS 문제이다. DFS 알고리즘을 활용하여 모든 경우를 탐색하고, 가장 큰 이익을 얻을 수 있는 경우를 출력하면 된다. ▶Solution
[BOJ] 백준 14499. 주사위 굴리기 ▶문제설명[BOJ] 14499. 주사위 굴리기 https://www.acmicpc.net/problem/14499 ▶Hint시뮬레이션 문제이다. 4 x 3 행렬에 주사위를 전개도로 나타내고, 주사위를 상/하/좌/우로 굴렸을 때 전개도 상태를 업데이트 해주면 된다. 처음에는 6면 모두 0으로 시작하며, 숫자판에서 주사위가 위치한 곳의 숫자가 0인 경우 주사위 밑바닥에 적힌 숫자가 점수판에 복사되고, 주사위 밑바닥에 적힌 숫자가 0인 경우 주사위가 위치한 곳의 숫자가 주사위 밑바닥에 복사된다. 주어진 입력에 따라 그대로 실행하되, 숫자판의 범위를 초과하는 경우는 무시한다. ▶Solution
[BOJ] 백준 3055. 탈출 ▶문제설명[BOJ] 3055. 탈출 https://www.acmicpc.net/problem/3055 ▶Hint매 초마다 물이 퍼져나가는 것을 먼저 처리한 뒤 고슴도치가 이동 가능한 경로로 이동하게 하면 된다. BFS를 활용하면 도착지까지 이동 가능한 모든 경로를 탐색해볼 수 있다. 도착지에 도달했을 때 걸린 시간이 가장 짧은 것을 정답으로 한다. ▶Solution
[BOJ] 백준 16235. 나무 재테크 ▶문제설명[BOJ] 16235. 나무 재테크https://www.acmicpc.net/problem/16235 ▶Hint ▶Solution123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143..

티스토리툴바