본문 바로가기

알고리즘/프로그래머스71

[프로그래머스] 여행경로 c++ 풀이 string을 방문한것을 어떻게 체크해 줄지 고민하다가 multimap을 써서 복잡하게 풀었다. #include #include #include #include #include using namespace std; vector answer; int city_cnt; multimapcnnt; vectorroute; mapvisit; bool chk; void dfs(int visit_cnt,string airport, vector& route){ if(visit_cnt==city_cnt){ if(chk) return; answer=route; chk=true; return; } if(visit_cnt>city_cnt) return; vector next_airport; //vector로 옮기기 aut.. 2024. 2. 10.
[프로그래머스] 아이템 줍기 c++ 풀이 bfs문제였다. 관건읜 직사격형의 외각만 딴 경로를 그리는 것이였다. 임의의 좌표에 대해서 어떠한 사각형 내부에 (선 제외) 있다면 외각선이 아니므로 체크해주지 않는다. 위의 조건을 통과하는 점들은 외곽선에 있는지 체크하고 좌표를 true로 바꾸어 주었다. 문제는 배열의 좌표만 가지고 판단한다면 3,5와 3,6 둘 다 true여서 이동할 수 있는 것처럼 보인다. (바로 옆에 있기 때문에) 해법은 검색해서 찾았다. 모든 좌표를 2배로 해서 계산하면된다. 그리고 답을 2로 나누어서 제출하면된다. #include #include #include #include using namespace std; vectorvisit(101,vector(101,false)); vectormap(101,vector(101.. 2024. 2. 10.
[프로그래머스] 단어 변환 c++ 풀이 단어하나하나를 노드라고 하고 단어마다 단 한개가 다를때 연결되어 있다고 생각하면 bfs로 풀면된다. target단어가 포함되어 있지않으면 0을 반환한다. #include #include #include #include using namespace std; int words_len; vectorcnnt_node[51]; bool visit[51]; int dist[51]; int ans_idx; vector words; int answer; int begin_size; int countSameChar(string a,string b){ int num=0; for(int k=0;k 2024. 2. 9.
[프로그래머스] 게임 맵 최단거리 c++ 풀이 bfs를 이용해 최단거리를 구하는 문제였다. bfs는 근접 노드를 다 방문하고 depth를 +1 해서 방문하기 때문에 근접 a와 인근한 b,c,d .. 노드들은 depth가 같고 즉 거리가 같다. 그렇기 때문에 b,c,d를 방문한 순서와 상관없이 b,c,d까지의 거리가 같다. ( ex) c,d,b순서대로 방문해도) 한 단계에서 갈 수 있는 모든 노드들을 방문하기 때문에 한 번 방문한 노드의 거리는 노드까지의 최단 경로가 된다. 효율성까지 맞기 위해서는이미 거리를 갱신한 노드는 또 거리를 갱신시켜주면 안된다. b에서 탐색을 해서 d의 최단거리를 3으로 갱신시켜주었다. c에서 탐색을 할때도 d의 최단거리는 3이 된다. 하지만 이미 갱신을 시켜주었기 때문에 불필요한 작업이 된다. 이는 34번째 줄의 cn.. 2024. 2. 7.

티스토리툴바