네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 2. 풀이 과정 1. (0, 0)에서 시작해서 치즈 있는 곳을 만나면, 치즈 있는 곳에 +1을 해준다. 2. 치즈가 있는 곳이 3이 되는 순간 2면이 외부와 닿아있다는 의미이므로 다음 탐색할 노드에 추가해준다. 3. next = 다음 탐색할 노드들의 모음으로 각 노드마다 dfs로 치즈 있는 곳을 만나면, 치즈 있는 곳에 +1을 하고 2단계를 반복한다. import java...

1. 문제 https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 2. 풀이 과정 MST 문제이고, kruskal와 prim이 떠올랐다. 두 가지 알고리즘을 각각 사용해서 두 번 풀어봤는데, 간선의 개수가 많기 때문에 kruskal보다 prim이 훨씬 빨랐다. 1. Kruskal 더보기 import java.io.*; import java.util.*; public class Main { static int N, p[]; public static Pr..

1. 문제 https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 2. 풀이 과정 처음 주어진 감염된 컴퓨터로 부터 다른 컴퓨터들이 몇 초 안에 감염되는지 확인해야 한다. 감염된 컴퓨터들 중에 시간이 가장 많이 걸린 시간이 감염하는 데 걸린 시간이다. 이때, 걸리는 시간이 모두 다르므로 BFS가 아닌 다익스트라를 사용해야 한다. import java.util.*; import java.io.*; public class Main { static int T,..

1. 문제 https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 2. 풀이 과정 bfs나 dfs 아무거나 편한 걸로 선택해서 풀면 되는 문제 같다. 아래 풀이에서는 돌아본 곳을 또 방문하지 않기 위해서 bfs를 썼다. 무조건 바깥 테두리엔 치즈가 없으므로, 테두리 0, 0에서 시작해서 1을 만나면 값을 0으로 바꾸고 Queue에 쌓아주었다. 또 다음 Queue의 요소를 돌면서 또 1을 만나면 같은 작업을 반복해주었다. 하지만 N, M의 크기가 작은 편이라 전..

1. 문제 https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 2. 풀이 과정 1. 사이클 찾기(DFS) 모든 경로를 돌다가 아래 두 조건을 만족하면, 사이클이므로 return true를 하고 사이클 요소에 true표시 1) 방금 전에 방문한 노드 != 다음에 방문할 노드 2) 이미 방문한 노드 dfs로 돌아가다가 출발점을 마주치면 return false로 사이클 요소 true표시를 종료한다. 2. 사이클에서부터 거리 찾..

1. 문제 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 2. 풀이 과정 1. 정렬 알고리즘이 필요없다. 삽입되는 값이 제일 작기 때문에, 순서대로 넣어주면 정렬된 상태이다. 차례대로 list에 add하면 내림차순으로 정렬되므로 뒤에서부터 탐색하도록 for문을 작성했다. 2. LinkedList vs ArrayList 순서대로 조회하는 일이 많으므로 ArrayList가 훨씬 효율적이다. 이 문제에서는 LinkedList로 풀이..

1. 문제 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 2. 풀이 과정 1. 순서 찾기 : 위상정렬 2. 정렬이 안 되는 경우는 자신 앞에 있는 노드 수가 0이상인 노드만 남았을 때이다. 이 경우, 사이클이기 때문에 주어진 조건을 모두 만족하는 순서를 찾을 수 없다. import java.io.*; import java.util.*; public class boj2623 { public static void main(St..

1. 문제 https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 2. 풀이과정 방문체크를 3개씩 하는 DFS 문제이다. 처음에 N, M이 5이하라서 방문체크를 비트마스킹으로 풀었는데, boolean으로 풀었을 때가 1.5배나 빨랐다. 비트마스킹은 배열이 아닌 int로 풀어서 2차원 배열 1차원 배열 전환하는 연산이 많아서 느렸던 것 같다. +) 벽세우기를 한 후, 1.5배 더 빨라졌다. import java.io.*; import ..

1. 문제 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 2. 풀이과정 이 문제는 dfs나 bfs 둘 중 하나로 풀 수 있을 것 같은데, dfs를 선택한 이유는 n, m의 최대 크기가 100으로 작은 편이라 stack이 최대 100x100개정도 밖에 안 쌓이며, 코드도 더 짧기 때문이다. import java.util.*; import java.io.*; public class boj1743 { sta..

1. 문제 https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 2. 풀이과정 1. 부모 정보를 배열에 받아서 저장한다. 2. 뒷번호부터 검사(leaf노드부터 검사하기 위함) 1) 해당 숫자를 부모로 가진 자식들의 직간접적으로 이어진 자식들의 수를 구해서 정렬한다. 2) 자식들 중 아래에 있는 자식들이 많은 것부터 차례로 순서를 부여한다. 3) 순서 + 아래에 있는 자식들의 수가 가장 큰 값을 해당 숫자에 기록하며 업데이트 해간다. import java...