■ 알고리즘 문제 풀이 (74) 썸네일형 리스트형 [BOJ] 백준 14503. 로봇 청소기 ▶문제설명[BOJ] 백준 14503. 로봇 청소기 https://www.acmicpc.net/problem/14503 ▶Hint시뮬레이션 문제이다. 네 방향을 회전하며 청소할 공간을 탐색하는 과정에서 청소한 공간을 찾았는지 찾지 못했는지 판단하는 플래그 역할의 변수를 활용하면 청소할 공간을 찾아서 청소를 한 경우와 그러지 못 한 경우를 분기점으로 하여 프로그램의 흐름을 바꿀 수 있다. ※ 청소할 공간이 없음 = 이미 청소를 했거나 벽임 로봇 청소기는 현재 위치에서 자신의 왼쪽 방향만 체크할 수 있다. 자신의 현재 방향에서 왼쪽만 보는 방법으로 네 방향을 모두 체크하면서 아래의 케이스를 확인하여 수행한다. (flag_go : OFF 상태로 시작) case 1. 아직 청소를 안 한 공간이 있음 : 왼쪽으로 .. [BOJ] 백준 16637. 괄호 추가하기 ▶문제설명[BOJ] 백준 16637. 괄호 추가하기https://www.acmicpc.net/problem/16637 ▶ 설계브루트 포스 문제이다. DFS로 해결할 수 있을 것으로 보인다. 1+2-3*4 위 식을 예로 들어, 문제의 조건에 따라서 괄호를 씌울 수 있는 모든 경우를 나열해보자.1+2는 괄호를 씌우나 마나 결과가 같다. 가장 앞에 위치하기 때문이다.1+2-3*4+5 1+2-3*(4+5) 1+2-(3*4)+51+(2-3)*4+51+(2-3)*(4+5)이렇게 5 가지 경우가 있다. 함수를 두 번 재귀호출 하여 구현할 수 있다. 1. 이전 계산 결과와 오른쪽에 있는 피연산자를 피연산자로 하여 현재 가리키는 연산자의 연산을 수행하는 함수 (왼쪽부터 순서대로 계산하게 됨)2. 이전 계산 결과와 오른쪽.. [BOJ] 백준 16918. 봄버맨 ▶문제설명[BOJ] 백준 16918. 봄버맨 https://www.acmicpc.net/problem/16918 ▶Hint시뮬레이션 문제이다. 폭파 시간을 관리하는 2차원 배열을 하나 만든다. 각 좌표에 폭탄이 설치될 때, 현재 시각 + 3의 값을 저장해서 활용하면 쉽게 해결할 수 있다. 설치된 폭탄들은 폭파 시간이 되면 폭파하면서 상/하/좌/우를 빈 공간으로 만드는데, 매 시간마다 모든 폭탄들을 확인하여 폭파 시간이 된 폭탄은 폭파시키면 된다. 또한, 봄버맨은 시간이 2의 배수일 때 폭탄을 설치할 수 있는 모든 곳에 새로운 폭탄을 설치한다. ▶Solution 마지막 수정 일시 : 2019.04.09 12:08 [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 이전 1 ··· 4 5 6 7 8 9 10 다음
