[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제의 해석은 다음과 같다. 2차원 배열에 1이 되어있는 부분은 색칠된 부분이고 동서남북으로 이루어져 있는 그림을 하나의 그림으로 보고 그 그림의 개수를 print하고, 그림들 중에 가장 많은 면적을 차지하는 그림의 1의 개수를 표현하는 것이다. 문제는 DFS로 방문처리해주면서 카운트와 면적을 구하면 된다. 코드(DFS) import java.util.ArrayList; import java.util.Colle..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 1595번: 북쪽나라의 도로 입력은 여러줄에 걸쳐 주어진다. 입력의 각 줄은 세 개의 양의 정수로 구성되어있는데, 각각은 차례대로 서로 다른 두 도시의 번호와 두 도시를 연결하는 도로의 길이를 의미한다. 모든 도로는 www.acmicpc.net 문제는 다음과 같다. 이미 방문한 도시는 다시 방문할 수 없고, A 도시와 B 도시 간에 가장 먼 거리를 재는 것이다. 그래서 가장 먼 거리를 계산해 보면 5번 노드에서 시작해서 1번, 6번, 3번 순으로 가면 총 거리 22로 제일 길다. 근데 입력 조건에 보면 뭔가 언제부터 언제까지 받아야 하는지 표시가 안 되어 있었다. 코드로 확인해 보자 코드 import java.util.ArrayList; impor..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 위 문제는 예시에서 보이는 것처럼 어떠한 두 수가 주어졌을 때 이들의 가장 가까운 공통 부모 노드를 찾는 것이다. 나는 그래서 그래프를 짤 때 다음과 같이 했다. 위 그림처럼 노드들이 참조할 때 부모 -> 자식이 아닌 자식 -> 부모로 참조하였고 단방향 참조로 하였다. 뭔가 그게 더 쉽고 빠르게 풀 수 있을 것 같았다.(뇌피셜) 코드 import java..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 17220번: 마약수사대 최근들어 세계적으로 마약과 관련한 사회적 문제들이 많이 발생하고 있다. 이에 따라 경찰은 마약 수사대의 한정된 인력이 허용하는 선에서 최대한 마약공급을 막고자 한다. 마약 공급책들은 www.acmicpc.net 문제는 다음과 같다. 마약 공급책 헤더가 여러 사람에게 마약을 뿌리면 그 사람들도 밑으로 계속 공급하게 되고, 만약 공급책이 잡히게 되면 그 밑에 사람들은 공급을 받을 수 없게 된다. 처음 예제를 보고 계속 풀었는데 틀렸다고만 하길래 질문하기에 보니 마약 공급책(헤더)이 한 명이 아닌 여러 명일 수 있다고 하였다. 그리고 거기서 제시해준 반례를 돌려도 답은 맞았으나 제출하니 틀리기만 하였다. 그래서 반례를 만들어서 ..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 25195번: Yes or yes 첫째 줄에는 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. ($1 \leq N, M \leq 100\,000$) 이후 $M$줄에 걸쳐서 간선의 정보를 나타내는 두 정수 $u$, $v$ 가 주어진다. 이는 정점 $u$ 에서 정점 $v$ 로 가는 www.acmicpc.net 이번 문제는 길이가 좀 길지만 문제는 간단하다. 곰곰이는 팬들이 있다. 그리고 곰곰이는 간선(양방향 아님)을 통해 팬미팅?을 하는데 투어를 하면서 곰곰이 팬들을 만나지 못하면 yes를 팬들과 만난다면 Yes를 출력하면 된다. Yes인 상황은 예시 그림에서 잘 설명해주었고 yes인 상황은 다음과 같다. 코드 import java.util.Ar..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제의 해석은 다음과 같다. map[n][n]의 지도가 있고 그 위에 집은 1로 표시되고 아무것도 없으면 0으로 표시된다. 그리고 이 집들이 동서남북으로 이루어지면 단지를 이루게 된다. 그래서 총 단지는 몇 개이고 단지마다 집이 몇 개인지 오름차순으로 정렬해서 표시해주면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 위 문제는 판다가 i, j 좌표부터 대나무를 먹는데 이때 다른 대나무를 먹기 위해선 기존에 먹던 대나무 숫자보다 많아야 한다. 근데 처음에 DFS로 풀다 보니 시간 초과가 계속 떴었다.. 그래서 질문 검색을 보니 DP를 활용해야 했던 것이었다. DFS를 돌면서 DP도 동시에 해줘, DP에서 가장 높은 값을 가져와야 한다. 코드 import java.util.Scanner; public class..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제는 알파벳으로 된 맵이 있는데 말이 0, 0부터 시작하여 중복되지 않는 알파벳만 이동할 수 있다. 예제 1번을 그림으로 표현한다면 첫 번째 경우의 수로 말은 C - A - D 순으로 방문할 수 있고, 두 번째 경우의 수는 위와 같이 순서는 똑같지만 가는 방향이 다르다. 따라서 dfs를 호출할 때는 먼저 main에서 한 번만 호출하는데 이때는 무조건 0, 0부터 시작할 것이다. 코드 import ..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제의 요약은 적록색약은 R과 G로 되어있는 구역은 볼 수 없고, B는 따로 볼 수 있다. 정상인은 모든 색을 다른 구역으로 볼 수 있다. 그림으로 설명해보자면 위의 그림은 적록색약이 아닌 사람이 볼 수 있는 색깔의 구역이고, 위의 그림은 적록색약인 사람이 볼 수 있는 색깔의 구역이다. 그러면 DFS를 돌릴 때 조건을 주면 되는데 그 조건과 작동 순서는 다음과 같다. 적록색약이 아닌 사람) map를 ..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 문제는 맵 안에 섬이 있는데 사람은 대각선으로 된 섬을 건너갈 수 있고 이렇게 건너갈 수 있는 섬들이 총 몇 개인가를 세는 것이다. 위 문제는 X, Y 좌표값을 이용하여 문제를 풀어야 한다. 문제를 보면 대각선의 섬까지 걸어갈 수 있으므로 나는 static으로 아래와 같이 설정했다. static int dx[] = {0, 0, -1, 1, -1, 1, -1, 1}; static int dy[] = {-1, 1, 0, 0, 1, 1, -1, -1}; 그리고 DFS를 사용하여 0, 0부터 주변에 섬들이 있는지 X, Y 축을 이용하여 검색하고 있으면 또 거기서 연결되는 섬이 있는지 체크를 하였다. 그 후, 없을 경우 다음 노드 중 방문하지 않았고 섬이 ..
