그래프

[백준] 15591 - MooTube (Silver) (자바 Java)

[Gold V] MooTube (Silver) - 15591 문제 링크 성능 요약 메모리: 299080 KB, 시간: 1452 ms 분류 너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 농부 존은 남는 시간에 MooTube라 불리는 동영상 공유 서비스를 만들었다. MooTube에서 농부 존의 소들은 재밌는 동영상들을 서로 공유할 수 있다. 소들은 MooTube에 1부터 N까지 번호가 붙여진 N (1 ≤ N ≤ 5,000)개의 동영상을 이미 올려 놓았다. 하지만, 존은 아직 어떻게 하면 소들이 그들이 좋아할 만한 새 동영상을 찾을 수 있을지 괜찮은 방법을 떠올리지 못했다. 농부 존은 모든 MooTube 동영상에 대해 “연관 동영상” 리스트를 만들..

[백준] 9328 - 열쇠 (자바 Java)

[Gold I] 열쇠 - 9328 문제 링크 성능 요약 메모리: 22360 KB, 시간: 184 ms 분류 너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 구현(implementation) 문제 설명 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다. 상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 ..

[백준] 7569 - 토마토 (자바 Java)

[Gold V] 토마토 - 7569 문제 링크 성능 요약 메모리: 130692 KB, 시간: 636 ms 분류 너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마..

[프로그래머스] 카카오프렌즈 컬러링북 (자바 Java)

[level 2] 카카오프렌즈 컬러링북 - 1829 문제 링크 성능 요약 메모리: 89.9 MB, 시간: 8.96 ms 구분 코딩테스트 연습 > 2017 카카오코드 예선 채점결과 정확성: 100.0 효율성: 0.0 합계: 100.0 / 100.0 문제 설명 카카오 프렌즈 컬러링북 출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.) 그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자...

[백준] 1987 - 알파벳 (자바 Java)

[Gold IV] 알파벳 - 1987 문제 링크 성능 요약 메모리: 12936 KB, 시간: 996 ms 분류 백트래킹(backtracking), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로..

[백준] 17244 - 아맞다우산 (자바 Java)

[Gold II] 아맞다우산 - 17244 문제 링크 성능 요약 메모리: 99772 KB, 시간: 360 ms 분류 너비 우선 탐색(bfs), 비트마스킹(bitmask), 브루트포스 알고리즘(bruteforcing), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다. 외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, ..

[백준] 9466 - 텀 프로젝트 (자바 Java)

[Gold III] 텀 프로젝트 - 9466 문제 링크 성능 요약 메모리: 303204 KB, 시간: 1344 ms 분류 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는..

[백준] 2206 - 벽 부수고 이동하기 (자바 Java)

[Gold IV] 벽 부수고 이동하기 - 2206 문제 링크 성능 요약 메모리: 339388 KB, 시간: 976 ms 분류 너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 칸..

[백준] 17135 - 캐슬 디펜스 (자바 Java)

[Gold III] 캐슬 디펜스 - 17135 문제 링크 성능 요약 메모리: 32012 KB, 시간: 312 ms 분류 브루트포스 알고리즘(bruteforcing), 그래프 이론(graphs), 구현(implementation), 시뮬레이션(simulation) 문제 설명 캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다. 성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다...

[알고리즘] 플로이드-워샬 알고리즘

플로이드-워샬 알고리즘 모든 쌍 최단 경로 알고리즘: 모든 정점 쌍 사이의 최단 경로를 구하는 방법 단순 최단 경로 알고리즘 m개의 간선을 사용해서 i에서 j까지 이르는 최단거리 모든 정점 k에 대해 최대 m-1개의 간선을 사용해서 i에서 k까지 이르는 최단거리 $d_{ik}^{m-1}$에다가 $w_{kj}$를 더한 값을 구하고, 이 중 가장 짧은 것을 택함 for (i=1 to n) for (j=1 to n) d(i to j, k=0) = w[i][j]; for (m=2 to n-1) for (i=1 to n) for (j=1 to n) d(i to j, k=m) = min(d(i to k, k=m-1) + w[k][j]) 시간 복잡도: $\theta(n^4)$ 플로이드-워샬 $d_{ij}^{k}$ =..