랄뚜기의 코딩일기

https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 전형적인 DFS,BFS 문제이다. 까다로운 점이 있다면 비트마스킹을 사용해야 한다는 점인데 아마 비트 마스킹을 공부 했던 분들이라면 쉽게 풀 수 있을 것이라고 생각한다. 한가지 더 어려운 점이 있다면 벽 하나를 뚫었을 때 가장 큰 방의 크기를 구하는 문제였는데 나는 모든 방에 색깔 정보와 해당 색깔의 방을 크기를 저장하였다. 모든 방을 방문하면서 상하좌우의 방과 색깔이 다를 경우 두 색깔의 ..

https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 알고리즘의 분류에 트리, dp 이렇게 적혀 있길래 한참 고민했다. BFS를 이용하여 각 depth마다 최소로 필요한 얼리어답터들을 저장하며 풀었는데 예외상황이 발생했다. 그래서 그냥 dfs에 조건을 넣어서 풀었다. 조건 1. 자식에 리프노드가 존재한다면 무조건 얼리어답터가 되야 한다. 2. 자식 중에 얼리어답터가 아닌 사람이 한 명이라도 존재한다면 부모는 얼리어답터가 돼야 한다. 이 조건을 ..

https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 처음에 보고 이게 왜 그래프 이론인지 생각했다. '그냥 조건 몇 개 넣고 돌리면 되겠네!'라는 안일한 생각을 가지고 10분 만에 짜서 제출했지만 바로 뜨는 틀렸습니다... 한 20분 정도 혼자 끄적이다 결국 다른 분들의 풀이를 봤다. 역시 내가 넣은 조건에는 예외가 존재했다. 모든 조건을 넣는 것은 매우 힘들기 때문에 필수 조건을 넣어주고 BFS를 돌리면 됐다. 경우의 수를 구..