이름 못 정한 블로그

문제 설명 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요. 제한사항 격자의 크기 m, n은 1 이상 100 ..

가장 먼 노드를 찾기 위해서 BFS를 적용할 수도 있었는데 나는 다익스트라 알고리즘을 적용해서 풀었다. 다익스트라는 한 노드에서 각 노드에 대해 가장 짧은 경로를 찾아준다. 따라서 다익스트라 결과에서 가장 큰 값을 찾고 같은 값이 몇개인지만 찾으면 된다. #include #include #include #define INF 1000000 using namespace std; int map[20001][20001]; int dist[20001]; bool visit[20001]; void Dijkstra(int start, int n){ int cur, min, min_idx; for(int i = 1; i

한문제만 풀기 섭섭해서 한 문제 더 풀었다. 원래는 DP에 있는 N으로 표현 문제를 풀다가 너무 어려워서 이 문제로 도망쳤는데 오히려 아까 푼 문제보다 더 빨리 푼 듯하다. 푸는데 5분 정도 걸린거 같다. 레벨3 치고는 너무 쉽거나 내가 DP를 겁나 못하거나 둘 중 하나겠지. 처음엔 union-find로 풀까 하다가 단순히 DFS만 돌려도 될 것 같길래 이렇게 풀었다. 어느 한 노드에서 DFS를 시작해서 끝났는데도 아직 방문하지 않은 노드는 다른 네트워크다. 따라서 모든 노드를 방문할 때까지 DFS를 돌리면 그 횟수가 네트워크의 개수가 된다. #include #include using namespace std; int visit[201] = { 0, }; void DFS(int cur, int n, ve..

백준만 풀기 섭섭해서 프로그래머스도 한문제 풀어봤다. 날먹하려고 가장 만만한 브루트포스로 풀었다. 근데 벡터 사용이 어색해서 좀 버벅였다...ㅋ 문제 자체는 아주 쉬웠다. #include #include using namespace std; vector solution(vector answers) { vector answer; int score[3] = {0, }; int idx[3] = {0, }; const int giver1[5] = {1, 2, 3, 4, 5}; const int giver2[8] = {2, 1, 2, 3, 2, 4, 2, 5}; const int giver3[10] = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; for(int i = 0; i < answers.siz..