본문 바로가기
반응형

Problem Solving/BOJ228

백준 21736번 헌내기는 친구가 필요해 - C++ 풀이 1. 현재 상황을 그래프로 나타낸다. 2. 도연이의 시작위치에서 시작하는 BFS/DFS를 수행한다. 3. 방문한 노드가 'P'인 경우 카운트한다. 1. 현재 상황을 그래프로 나타낸다. 주어진 상황은 그래프로 변환할 수 있다. 벽이 아닌 칸을 노드로 생각하고, 상하좌우로 인접한 칸들을 간선으로 잇는다. 2. 도연이의 시작위치에서 시작하는 BFS/DFS를 수행한다. 도연이와 A라는 노드가 연결되어 있다면, 도연이는 A를 만날 수 있다는 뜻이다. 도연이와 연결된 노드를 모두 찾기 위해 'I' 노드에서 시작하는 BFS/DFS로 그래프를 탐색하자. 3. 방문한 노드가 'P'인 경우 카운트한다. 각 노드를 방문하면서 해당 노드가 'P', 즉 사람인 경우 도연이가 해당 사람을 만날 수 있음을 의미하므로 카운트 + 1.. 2023. 7. 9.
백준 20529번 가장 가까운 세 사람의 심리적 거리 - C++ 풀이 1. 33명의 사람을 16개의 mbti로 분류하는 경우, 최소한 한 mbti에는 반드시 3명이상 속하게 된다. 2. 32명 초과인 경우 심리적 거리의 최솟값은 0이다. 3. 32명 이하인 경우 심리적 거리의 최솟값은 브루트포스로 구할 수 있다. 1. 33명의 사람을 16개의 mbti로 분류하는 경우, 최소한 한 mbti에는 반드시 3명이상 속하게 된다. 비둘기집의 원리란 "n+1 마리의 비둘기가 n개의 비둘기 집에 나누어들어간다면, 적어도 한 집에는 반드시 두 마리 이상의 비둘기가 들어가게 된다"는 원리이다. 이것을 현재 문제에도 적용할 수 있다. 사람 = 비둘기, mbti 종류 = 비둘기집으로 생각하면 된다. mbti가 16종류가 있으므로, 만약 사람이 16+1=17명 있다면, 적어도 한 mbti에는 .. 2023. 7. 6.
백준 14940번 쉬운 최단 거리 - C++ 풀이 1. BFS를 사용하여 두 지점 사이의 거리를 구할 수 있다. 2. BFS의 출발 노드를 목표지점으로 설정하여 모든 칸까지의 거리를 한번에 계산한다. 1. BFS를 사용하여 두 지점 사이의 거리를 구할 수 있다. 각 칸을 노드로 생각하고 갈 수 있는 땅끼리는 연결하여 그래프를 만든다. 이제 BFS를 사용하면 두 지점 사이의 거리를 구할 수 있다. 2. BFS를 사용하여 목표지점에서 모든 칸까지의 거리를 한번에 계산한다. 각 칸에서 출발하여 목표지점까지 도달하는 BFS를 수행한다면, 총 n^2개의 칸에 대해 O(n^2)의 시간복잡도가 소요되므로 총 시간복잡도는 O(n^4)가 되어 시간초과를 받을 수 있다. 거꾸로 목표지점에서 출발하여 모든 칸을 방문하는 BFS를 진행하면 한번에 계산이 가능하다. 각 노드를.. 2023. 7. 6.
백준 10800번 컬러볼 - C++ 풀이 1. 공들을 크기 오름차순으로 정렬한다. 2. i번째 공이 사로잡을 수 있는 공들의 크기합 = (i번째 공보다 작은 공들의 크기합) - (i번째 공보다 작고 색이 같은 공들의 크기합) 1. 공들을 크기 오름차순으로 정렬한다. 먼저 공들을 크기 기준으로 오름차순 정렬해준다. 2. i번째 공이 사로잡을 수 있는 공들의 크기합 = (i번째 공보다 작은 공들의 크기합) - (i번째 공보다 작고 색이 같은 공들의 크기합) i번째 공보다 크기가 작고 색이 달라야 하므로, (i번째 공보다 작은 공들) - (i번째 공보다 작고 색이 같은 공들)을 구하면 된다. 포인터를 하나 두고, 포인터가 가리키는 공의 크기가 현재 공의 크기와 같아지기 전까지 포인터를 오른쪽으로 이동시키면서 1. 전체 크기 합과 2. 색깔별 크기 합.. 2022. 10. 5.
백준 16954번 움직이는 미로 탈출 - C++ 풀이 1. 상태 노드를 나타내기 위해 필요한 값은 {시간, 행, 열} 값이다. 2. BFS를 사용하여 {0, 7, 0}에서 {t, 0, 7}에 도착할 수 있는지 확인한다. 1. 상태 노드를 나타내기 위해 필요한 값은 {시간, 행, 열} 값이다. 시간이 지남에 따라 미로가 바뀌고 있으므로, 상태 노드를 나타내기 위해 필요한 값은 행, 열, 그리고 시간 값이다. 2. BFS를 사용하여 {0, 7, 0}에서 {t, 0, 7}에 도착할 수 있는지 확인한다. BFS를 사용하여 시작 노드 {0, 7, 0}에서 {t, 0, 7}에 도착할 수 있는지 확인한다. 언제 도착했는지는 상관이 없기 때문에 r=0, c=7인 노드인지만 확인하면 된다. #include #include using namespace std; typedef.. 2022. 9. 30.
반응형

티스토리툴바