Be a developer

한 번 연산할 때 출력할 문자열의 길이가 1증가 하므로 가중치가 1이라 할 수 있고, 필요한 최소 문자열의 길이를 구하는 것이므로 bfs로 풀 수 있다. 일단 string으로 문자열을 저장했더니 시간 초과가 났다. char로 저장해서 출력하자. 다음으로, 주석 친 부분처럼 l과 r연산을 했더니 틀렸다. 1000과 같이 0이 포함된 연산을 제대로 풀지 못해서 였다. 만약 처음 푼대로 l연산을 하면 16은 61이 된다. 하지만 16은 0016이므로 160이 되어야 한다. 덤벙대지 않고, 문제를 똑바로 보고 풀도록 하자! 따라서 코드는 아래와 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ..

앞선 숨바꼭질 문제와 같다. 추가된 것이 있다면 답을 찾아가는 경로를 출력해야 한다. 그래서 경로를 저장하기 위한 배열 d를 하나 더 둔다. 도착지에서부터 출발지로 가면서 stack에 쌓은 후 pop하면서 출력한다. 물론 재귀 함수 호출을 통해서 출력해도 된다. 코드는 아래와 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include #include #include using namespace std; int time..

최소 거리를 구하는 문제이고, 한 칸 이동하는 것이 가중치 1이므로 bfs로 풀 수 있다. 먼저 물이 퍼지는 데 걸리는 시간을 dist 배열에 저장하고, 고슴도치가 이동하는 것을 따로 visit 배열에 저장한다. 즉, bfs를 두 번 돌린다. 계속 틀렸다고 나오는 데 무슨 문제인지는 잘 모르겠지만, 조건을 걸러 내는 것이 매우 까다로운 문제인 것 같다. 조건을 통해 queue에 넣을 조건을 잘 거르는 것이 중요한 문제인 것 같다. 매우 짜증나게 시간 오래 잡아먹음 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 4..

최단 경로를 구하는 문제이고, 한 칸 이동하는 것을 가중치 1로 둘 수 있으므로 bfs로 풀 수 있는 문제다. 벽을 1번 부순 경우와 벽을 부수지 않은 상태로 이동하는 경우가 다르기 때문에 다른 정점으로 봐야 한다. 따라서 3차원 배열로 선언하여 벽을 부쉈을 때 비용과 부수지 않았을 때 비용을 구분하여 준다. 그리고 queue에는 벽을 부쉈는지 여부도 전달해주어야 한다. 처음에는 [row][col][0]에 비용을 저장하고, [row][col][1]에 벽을 부순 여부를 저장했는데, 이는 어느 특정한 칸을 왔을 때 벽을 한 번 부쉈는지 안 부쉈는지 경우의 수를 나누지 않은 것이었다. 아래는 처음 생각했던 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2..

벽을 부수고 이동하면 가중치가 1이고, 부수지 않고 이동하면 가중치를 0이라 생각할 수 있다. 벽을 최소로 부수는 것을 구해야 하므로, 벽을 부수지 않는 경우의 수를 앞선 queue에 넣고, 부수는 경우의 수를 next_queue에 넣으면 된다. 그렇게 생각하면 앞서 풀어본 문제처럼 두 개의 queue로 나누어 풀 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 #include #incl..

bfs는 모든 가중치가 1일 때 가능하다. 앞서 풀었던 숨바꼭질 문제는 수빈이가 이동할 때 모두 1초가 걸렸기 때문에 가능했다. 하지만 이번 문제는 0초에 이동할 수 있어서 가중치가 0인 경우가 있다. 원래 bfs는 queue에 넣는 건데, 다 가중치가 1이기 때문에 거리가 1일 때, 거리가 2일 때 차곡차곡 쌓인다. 하지만 가중치가 다르면 꺼냈을 때 값이 뒤죽박죽이 된다. 이럴 경우에 queue를 여러 개 사용해서 푼다. 즉, 0초 일 때 넣을 queue와 1초 일 때 넣을 queue 총 2개를 사용해서 문제를 푼다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #..

연산에 1초가 걸리기 때문에 가중치가 1이고, 시간의 최솟값을 구하는 문제이므로 bfs로 풀 수 있는 문제다. 화면에 있는 이모티콘의 수를 인덱스로 하는 배열을 만들고, 해당 개수를 화면에 띄우는데 걸리는 시간을 인덱스에 해당하는 값으로 넣으려고 했다. 하지만 각 화면에 뜨는 갯수가 같아도 클립보드에 있는 이모티콘의 개수는 각각 다르기 때문에 계산이 복잡해진다. 즉, 화면에 있는 이모티콘의 개수가 같아도 클립보드에 있는 이모티콘의 갯수가 다르면 다른 상태가 되는 것이다. 결론적으로 하나의 정점을 나타내는 데 필요한 정보가 2개인 것이다. 따라서 화면에 있는 이모티콘의 개수를 s, 클립보드에 있는 이모티콘의 개수를 c라 하면 하나의 정점은 (s, c)로 나타낼 수 있다. 따라서 2차원 배열을 사용한다는 것..

앞에 문제들과 다르게 그래프처럼 생긴 문제들을 bfs로 푸는 것이 아니라, 그래프처럼 보이지 않는 문제를 그래프로 바꾸어 bfs로 푼다. 한 번 이동하는데 1초가 걸리므로 가중치를 1로 생각할 수 있다. 최대 위치가 10만이므로 bfs로 풀 수 있다. 처음에는 dist 배열만 선언해서 방문할 때마다 1을 더해주었다. 어짜피 한 번 방문하고 나서 이후에 방문하면 그 값이 더 커지므로 최소 비용을 만족할 수 없다고 생각했기 때문이다. 계속 틀렸다고 나와서 생각해보니, 첫 시작점도 dist는 0이기 때문에 계속 반복해서 방문하게 되는 문제가 발생한다. 이를 수정했더니 맞게 나왔다. 자세한 설명은 주석으로.. 123456789101112131415161718192021222324252627282930313233..