Problem solving/Programmers6 [Programmers] 아이템 줍기 (C++) 문제 직사각형들을 겹친 후 둘레를 따라 이동한다. 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리는? 생각할 것 겹친 사각형들의 테두리를 구해야 할 것이다 안쪽을 모두 1로 채운 뒤에 안쪽을 다시 비워서 테두리를 찾는다 테두리가 인접한 경우 배열만 보고 테두리를 판단할 수 없다 모든 좌표값을 2배로 늘린다. 물론 배열의 크기도 2배로! BFS로 최단 경로를 탐색한 뒤 경로를 다시 2로 나누어준다. 코드 #include #include #include #include using namespace std; int solution(vector rectangle, int characterX, int characterY, int itemX, int itemY) { int answer = 0; // 사각.. 2023. 7. 6. [Programmers] 여행경로 (C++) 문제 주어진 항공권을 모두 이용해서 여행경로 짜기 항상 ICN공항에서 출발 가능한 경우가 여러가지 있다면 알바벳 순의 경로를 리턴 생각할 것 ICN에서 출발 주어진 항공권을 모두 사용하기 위해 백트래킹 사용하기 코드 #include #include #include #include using namespace std; vector visited; vector routes; vector route; void dfs(int ticketNum, vector tickets) { if(route.size() == tickets.size()) { route.push_back(tickets[ticketNum][1]); // 마지막 도착지점을 추가해주고 routes.push_back(route); route.pop_ba.. 2023. 7. 5. [Programmers] 단어 변환 (C++) 문제 두 개의 단어 begin, target과 단어의 집합 words가 주어진다. 아래의 규칙으로 begin에서 target으로 변환하는 가장 짧은 변환 과정 찾기 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예시 ) begin : “hit” target : “cog” words : ["hot","dot","dog","lot","log","cog"] 변환 과정 : "hit" -> "hot" -> "dot" -> "dog" -> "cog” 생각할 것 백트래킹을 사용해서 모든 경우를 탐색 발견한 최소 탐색거리보다 크면 더 이상 탐색을 진행하지 않음 단어가 하나만 다른지 체크 코드 #include #include #include #include us.. 2023. 7. 5. [Programmers] 게임 맵 최단거리 (C++) 문제 상대 팀 진영에 도착하기 위해 지나가야 하는 칸의 최소 개수 찾기 도착할 수 없는 경우에는 -1 리턴 1은 지나갈 수 있는 곳, 0은 지나갈 수 없는 곳 생각할 것 최단거리를 구하는 것이므로 BFS 이용하기 코드 #include #include #include using namespace std; int dx[4] = {-1, 1, 0, 0}; // 상하좌우 int dy[4] = {0, 0, -1, 1}; int solution(vector maps) { int answer = -1; int n = maps.size(); int m = maps[0].size(); vector visited(n, vector(m)); queue q; // 상대 진영에서 시작 q.push({n-1, m-1}); vis.. 2023. 7. 5. 이전 1 2 다음
