반응형 DFS5 [SWEA/C++] DAG 동전 게임 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 설명을 잘 이해해야 쉽게 풀 수 있는 문제다. 먼저 조건을 보면 사이클이 있으며 위상 정렬이 되어있다.이를 이용하면 DFS로 1번 노드부터 시작해 N번노드와 N-1번 노드에 도착하는 경우에 돈을 얼마 미만 갖고 있어야 하는지 파악 할 수 있다. 먼저 그림을 통해 예를 들어 보자. 위 그림과 같은 경우에는 N-1과 N으로 바로 가는 방법이 있다.그러므로 다현의 돈의 비율이 나연의 비율과 같은 1:1 미만이면 무조건 나연이 승리한다는 사실을 알 수 있다. 이번에는 조금 다른 경우를 그려보자 위 그림을 보면 N-1과 직접 연결된 경로가 있으면 가진 돈을 전부 제시해 N-1로 가도록 유도할 수 있.. 2024. 11. 26. [프로그래머스/C++] 등대 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 주의해야하는 점이 A와 B 등대가 있다면 두 등대 중에 한 등대는 무조건 켜져있어야 한다는 점이다. 위 그림과 같이 등대가 켜져 있어도, A와 B 등대 사이에 불이 켜져있지 않기 때문에 정답이 될 수 없다. A와 B 등대중 하나가 켜져있어야 된다. 이제 문제를 풀때 사이클이 없으므로 하나의 트리로 볼 수 있다. 이를 이용해 1을 트리의 최상단 노드라고 가정하고, leaf 노드를 찾는다. 여기서 leaf 노드를 찾을 경우 leaf 노드의 불을 켜는 것 보다 부모 노드의 불을 켜는게 더 좋다. 왜냐하면 leaf 노드는 연결된 노드가 하나이고, leaf 노드의 부모 노드는 최상단 노드인 1을 제외하면 연결된.. 2024. 2. 7. [프로그래머스/C++] 네트워크 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] 컴퓨터와 컴퓨터가 연결되어 있으면 하나의 네트워크로 본다. 만약 A와 B컴퓨터 B와 C컴퓨터가 연결되어있다면, 하나의 네트워크로 간주한다. 컴퓨터간의 연결이 2차원 vector로 주어지면 컴퓨터들 간의 총 네트워크의 수는 얼마인지 return 하면 되는 문제다. HTML 삽입 미리보기할 수 없는 소스 컴퓨터의 개수가 최대 200개로 크지 않았기 때문에 DFS로 쉽게 풀 수 있다는 생각이 들었다. 그래서 이미 네트워크로 체크했는지 검사하는 isNet이라는 1차원 vector를 이용해 DFS로 문제를 풀었다. 하나의 컴퓨터와 연결된 컴퓨터는 이미 연결된 네트워크인지 체크를 했다고 처리를 하는 것이다. [아이디어 정리] 컴퓨터의 개수만큼 for문을 .. 2024. 1. 7. [프로그래머스/C++] 퍼즐 조각 채우기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [풀이] 처음에 문제를 보고 빈 공간에 조각을 채워넣어야 하는 줄 알고 어렵다고 생각했는데, 조건에 조각을 넣었을 때, 빈 공간이 생기면 안된다는 조건을 보고 생각보다 쉽겠다고 생각했다. 하지만 막상 해보니 코드가 엄청 길어지고 처음 생각했던 방법과 다르게 풀어서 의외로 오래 걸렸다... 내가 시도한 방법은 조각이 들어갈 수 있는 공간을 탐색하고, 그 공간의 모양을 파악해 90도로 회전해 나올 수 있는 모양들은 전부 같은 모양으로 정했다. 그리고 조각의 모양이 90도로 회전해 나올 수 있는 모양 중 하나라면 채워넣는 식으로 코드를 짰다. 이후 같은 조각인지 비교하는 방법은 다음 그림과 같이 만들었다. 만약 위와 같은 퍼즐의 공.. 2024. 1. 7. [백준/Python] 17070번 - 파이프 옮기기1 HTML 삽입 미리보기할 수 없는 소스 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다. 파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다... 2024. 1. 2. 이전 1 다음 반응형
