카테고리: BOJ

백준 효율적인해킹 1325

1. 백준 효율적인 해킹 문제 1.1. 컴퓨팅적 사고 양방향그래프가 아닌 단방향그래프인것을 파악하여 연결된 해킹의 컴퓨터개수를 구하는 문제였습니다. 처음에 양방향 그래프로 생각을 하여서 a->b, b->a에 대한 양방향 설정을 진행하였는데, 올바른 결과가 나오지 않았습니다. 문제를 다시 잘 읽어보니 B의 컴퓨터를 통해 A의 컴퓨터를 해킹을

백준 상근이의 여행 9372

1. 백준 상근이의 여행 문제 1.1. 컴퓨팅적 사고 이 문제의 가장 핵심포인트는 비행기의 종류를 구하는것이다. 비행기의 종류를 구하는것이 결국 간선의 개수가 몇개인것인지에 대한 문제이다. 즉, n-1이다 다른방식으로는 bfs로 체크되지 않은정점과 값이 있는 정점을 방문할 수 있을때마다 answer를 카운팅시켜주면서 가능한 모든 비행기 종류를 체크합니

백준 순열사이클 10451

1. 순열사이클 문제 1.1. 컴퓨팅적 사고 순열사이클을 구하는문제이다. 사이클이 발생하면 dfs를 수행하였을때 모든값들이 check가 되어있을것이다. 따라서, 매번 순회할때마다 체크가 안된지점만 확인을 하면 최종적으로 몇개의 사이클이 만들어지는지를 알 수 있다. 테스트케이스로 3, 2, 7, 8, 1, 4, 5, 6일 경우 1~N까지의 수가 매칭이

백준 케빈 베이컨의 6단계 법칙 1389

1. 문제 1.1. 컴퓨팅적 사고 플로이드 워셜 알고리즘 11403번 경로찾기와 다르게 최단 경로의 비용을 구하는 문제이다. 예를들면, 1번 노드에서 -> 2번, 3번, 4번, 5번 ,6번을 거쳐간 비용의 총합이다. 단순히 경로찾기문제는 비용이 문제가 아니라 해당되는값이 존재하는지 안존재하는지 여부만 찾았다. 자기 자신의 값을 0으로 초기화하고

백준 경로찾기 11403

1. 경로찾기 문제 1.1. 컴퓨팅적 사고 모든정점에서 다른정점까지 모두 탐색할 수 있는지 판별하는 문제이다. 따라서 플로이드 워셜 알고리즘을 사용하면 모두 구할 수 있고 n의 범위가 100이하이기때문에 n^3 플로이드 워샬알고리즘을 사용하였다. 즉, 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘입니다. 다익스트라 알

백준 부모의 트리찾기 11725

1. 트리의 부모찾기 문제 1.1. 컴퓨팅적 사고 인접리스트로 해당되는 그래프를 연결시킨다. dfs로 해당되는 모든 부모의 값을 배열 갱신시킨다.(단 루트노드는 1번 부터 시작된다.) 시작점 예) parent[y] = x 최종적으로 parent에는 각 노드 2번부터 n번까지 부모의 값이 담겨져 있다. 1.2. 소스코드

백준 촌수계산 2644

1. 촌수계산 문제 1.1. 컴퓨팅적 사고 부모자식관계를 트리형태로 나타낸다. 시작점으로부터 각각의 depth + 1을 늘려나가면서 몇촌 (즉, 촌수는 depth를 나타낸다.) DFS, BFS로 해당되는 값을 전파하면서 늘려나간다. 두가지 방법으로 풀이를 진행하였다. isCheck변수에 해당되는 depth를 저장시키고 저장된 값이 0일경우 -1, 그게

백준 A->B 16953

1. BOJ 16953 문제 1.1. 컴퓨팅적 사고 거꾸로 생각하거나 dfs로 풀기 10^9로는 모든경우를 체크할 수 없다. 다른방법을 구해야한다. bfs같은경우는 모든 경우를 구하는것은 가까운것만 탐색하므로 bfs로 처리할 수 있다. 범위가 10^9이기때문에 int의 범위로는 모두 처리하지 못한다. 따라서 Long으로 처리하니까 정답을 도출하였다.

백준 숫자판별하기 22101

1. 백준 숫자판별하기 22101번 1.1. 컴퓨팅적 사고 하나의 그래프 클래스를 만들어서 모든 맵의 x,y좌표로 생성한다 DFS를 수행하여 모든맵의 x,y좌표를 순회한다. 종료조건은 cnt의 개수가 6개가 만족되면 종료한다. 총 4가지 방향으로 동서남북의 direction 변수로 핸들링을 진행한다. isCheckRange함수에 맞게 이동한 값이 범위

백준 Mootube 15591

1. 백준 MOOTUBE 15591 문제 1.1. 문제 농부 존은 남는 시간에 MooTube라 불리는 동영상 공유 서비스를 만들었다. MooTube에서 농부 존의 소들은 재밌는 동영상들을 서로 공유할 수 있다. 소들은 MooTube에 1부터 N까지 번호가 붙여진 N (1 ≤ N ≤ 5,000)개의 동영상을 이미 올려 놓았다. 하지만, 존은 아직 어떻게