[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 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 축을 이용하여 검색하고 있으면 또 거기서 연결되는 섬이 있는지 체크를 하였다. 그 후, 없을 경우 다음 노드 중 방문하지 않았고 섬이 ..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 문제는 위와 같다. 이 문제 또한 전 게시글과 똑같은 방식이었다. [DFS] 프로그래머스 - 네트워크 문제 JAVA 풀이 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제는 9hyuk9.tistory.com 따라서 같은 방식을 적용해보면 메인 코드에서 노드들이 방문했는지를 체크하여 안 했을 경우 DFS를 돌리고 count++ 해준다. 그렇게 돌리다 보면 서로 간선이 끊겨있는 노드들은 check 배열에서 false가 되어있을 것이다. 그러면 그 노드들을 다시 DFS를 돌리고 count++을 해주면 ..
[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!] 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제는 다음과 같다. 예를 들어 [[1, 1, 0], [1, 1, 1], [0, 1, 1]]으로 이루어진 컴퓨터들이 있으면 자신의 컴퓨터 외에 다른 컴퓨터와 간선으로 이루어져 네트워크를 구성하는데 이때 네트워크 그룹의 위의 사진과 같이 세는 문제였다. 코드 class Solution { int[][] coms; static boolean[] check; int n; public boolean[] dfs(int x){ check[x] = true; for..
