graph23 [백준 11559] Puyo Puyo [Python] 문제뿌요뿌요의 룰은 다음과 같다.필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다.뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.남규는 최근 뿌요뿌요 게임에 푹 빠졌.. 2024. 7. 22. [엘리스 알고리즘 코드 챌린지 시즌 2] 예선 4일 [Python] 풀이루트가 1번인 트리에서 하나의 말을 "두 사람이 최적으로" 번갈아가며 점수를 얻고 말을 이동하는 문제다.문제에서 주어진 두 사람이 최적으로 라는 지문의 의미는 결국 시작 정점을 기준으로 자신의 점수를 가장 높이는 방향으로 게임을 끝내는 것을 의미한다. 우선 간선을 입력받아 양방향 그래프를 생성하자.이제 dfs로 리프노드까지 탐색하며 역순으로 부모노드에 대한 점수를 계산하고자 한다.양방향 그래프이므로 자식 노드로만 탐색을 해주자.리프노드 까지 탐색을 완료했다면 가장 적은 점수차를 dp에 갱신해주자.만약 자식이 없다면(리프노드) 자신의 번호가 자신의 점수가 되므로 diff를 0으로 계산해주자. 예선 3일차에서도 유명한 문제임에 비해 예외가 적용되지 않는 오류가 있었고, 제공되는 자료와 맞지않는 문제가 주.. 2024. 7. 12. [백준 06798] Knight Hop [Java] 문제Below is an 8 × 8 chessboard on which we will designate square locations using the ordered pairs as indicated. For example, notice that piece A is at position (2, 2) and piece B is at position (4, 3).A knight is a special game piece that can leap over other pieces, moving in the “L” pattern. Specifically, in the diagram below, K represents the knight’s starting position and the numbers 1 throu.. 2024. 7. 7. [백준 05567] 결혼식 [Java] 문제상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다. 출력첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.풀이상근이의 친구와, 친.. 2024. 7. 1. [2024 KAKAO WINTER INTERNSHIP] 도넛과 막대 그래프 [Python] 풀이도넛, 막대, 8자 그래프의 수와 이를 연결하는 중앙 정점의 번호를 구하는 문제다.문제에서 그래프 수의 합은 2 이상이라고 주어졌다.때문에 2개 이상의 단방향 연결을 가지는 정점이 중앙 정점이 될 수 있다.edges에 대해 다른 정점으로 단방향 연결을 하는지( out ) 연결 되는지( in ) dict을 활용해 기록해 주자.그래프를 완전 탐색하지 않고, 문제를 해결하는게 중요하다.각 그래프별 특징을 구해서 선형 탐색으로 풀이해보자. 우선 도넛 모양 그래프의 경우 단순히 단방향 연결 여부로만 판단하기에는 그렇다할 특징이 없다.막대 그래프의 경우 out이 존재하지 않는 정점이 1개 있다. 8자 그래프의 경우 out이 2개고, in이 2개인(0이 아닌) 정점이 존재한다.만약 in이 0이라면 그 정점은 중앙.. 2024. 6. 22. 이전 1 2 3 4 다음
