알고리즘 분류에는 문자열만 있지만, 나는 투포인터로 접근했다. 다른 사람들의 풀이를 보니, 한 칸씩 이동하며 연속된 IOI들의 개수를 세고 그 값이 N과 같아지면 answer를 카운팅하는 방식이다. 내가 실버 문제를 너무 복잡하게 생각한 것 같다. 아무튼 내 풀이 방법은 다음과 같다.
left와 right 포인터를 두고, 두 포인터의 거리가 2*n가 될 때까지 움직이며 조건을 확인한다. 기본적으로 left는 고정하고 right를 움직이는데, 한 칸 전의 문자와 현재 문자가 같다면 조건을 만족하지 않기 때문에 left 위치를 right로 확 옮겨준다.
만약 길이가 2*n을 만족하는 경우에는 left, 즉 시작 위치가 I로 시작하는 게 맞는지 확인한다. 아니라면 한 칸을 이동시켜 준다. 만약 맞다면 Pn의 조건을 만족하는 경우가 되는 것이다. answer의 값을 1 늘려주고, 이미 left~right 사이의 문자들은 IOI...IOI 를 만족하는 상태이기 때문에 바로 다음 I의 위치에서 시작할 수 있도록 left에 2를 더해줬다.
package week8;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BJ5525 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
String input = br.readLine();
int left = 0, right = 1, answer = 0;
char pre, cur = input.charAt(left);
while(right < m){
pre = cur;
cur = input.charAt(right);
// 동일한 문자가 연속됨
if(pre == cur) left = right;
// n 조건을 만족하는 길이가 됨
if(right - left == 2*n){
if(input.charAt(left) == 'O'){
left++;
}
else {
answer++;
left += 2;
}
}
right++;
}
System.out.println(answer);
}
}
이 문제는 연산을 전부 기억할 필요 없이 단순히 뺄셈의 유무만 확인하면 된다. 만약 '-'가 한번이라도 나온다면 그 뒤는 모두 음수로 처리가 가능하기 때문이다. 그런데 내 코드는 자바의 문자열 처리 기능을 제대로 활용하지 못한 풀이인 것 같다. 자바 문법으로 c++ 코드를 짠듯한 느낌..
여러 알고리즘이 합쳐져 있어서 구현 난이도가 꽤 빡센 문제였다. (170줄...) 크게 나눠보면
1. bfs로 서로 땅이 연결된 섬들을 구함
2. 각 섬들 간에 연결 가능한 다리를 찾음
3. 크루스칼로 다리 길이의 최소 합을 구함
의 과정으로 진행된다. 이제 하나씩 자세히 들여다보자.
먼저 1번에서는, 지도가 최대 10x10으로 작으므로 한 칸씩 이동하며 1을 발견한다면 연결된 땅들을 하나의 섬으로 표시해준다. 0은 바다, 1은 땅이므로 섬의 번호는 2번부터 시작하도록 했다. 나중에 크루스칼 알고리즘을 돌리며 모든 섬이 연결되었는지를 확인하기 위해서는 섬의 개수가 필요하기 때문에, 섬의 번호를 표시함과 동시에 총 섬의 개수를 리턴해준다. 이 때, 섬의 번호는 2부터 시작했기 때문에 2를 뺀 값을 리턴했다.
2번에서도 마찬가지로, 지도가 작기 때문에 한 칸씩 이동하며 섬이 나온다면 근처 섬을 찾도록 한다. 다만 상하좌우 4방향을 모두 볼 필요는 없다. A섬에서 아래로 내려가 B섬과 만나는 다리를 찾았는데, B섬에서 위로 올라가 A섬과 만나는 다리를 또 찾게된다면 동일한 다리를 두번 탐색하게 되기 때문이다.
0이면 바다이므로 다리의 길이를 +1해주고, 시작 지점의 번호와 같다면 내륙을 통한 것이기 때문에 넘어간다. 아예 다른 번호가 나온다면 근처 섬을 찾은 것이다. 그렇게 Edge를 만들어 우선순위 큐에 넣어준다.다리를 찾았더라도 그 길이가 1이라면 넘어가야 한다.
이제 복잡한 전처리는 모두 끝났으니, 3번에서는 익숙한 크루스칼 알고리즘을 돌려주면 된다. 그런데 모든 섬이 연결되지 않는 경우가 존재할 수 있으므로, 연결된 다리의 수와 섬의 수를 비교해야 한다. bridgeCnt = islandCnt -1이라면 모든 섬이 연결된 것이고, 아니라면 -1을 출력해야 한다.
코드
package week7;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BJ17472 {
static class Pos{
int x, y;
public Pos(int x, int y) {
this.x = x;
this.y = y;
}
}
static class Edge implements Comparable<Edge>{
int from, to, dist;
public Edge(int from, int to, int dist) {
this.from = from;
this.to = to;
this.dist = dist;
}
@Override
public int compareTo(Edge o) {
return this.dist - o.dist;
}
}
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int[][] islandMap;
static int[] root;
static int n, m;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
// 변수 초기화
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
islandMap = new int[n][m];
// 지도 정보 저장
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++)
islandMap[i][j] = Integer.parseInt(st.nextToken());
}
// 섬 찾기
int islandCnt = findIsland();
// 섬들 간의 거리 계산
PriorityQueue<Edge> pq = findBridge();
// 크루스칼 알고리즘
System.out.println(kruskal(pq, islandCnt));
}
private static int kruskal(PriorityQueue<Edge> pq, int islandCnt) {
int bridgeCnt = 0;
int bridgeLen = 0;
root = new int[islandCnt+2];
for (int i = 0; i < islandCnt+2; i++)
root[i] = i;
while(!pq.isEmpty()){
if(bridgeCnt == islandCnt - 1) break;
Edge e = pq.poll();
int r1 = findRoot(e.from);
int r2 = findRoot(e.to);
if(r1 == r2) continue;
union(r1, r2);
bridgeCnt++;
bridgeLen += e.dist;
}
return bridgeCnt == islandCnt-1 ? bridgeLen : -1;
}
private static PriorityQueue<Edge> findBridge() {
PriorityQueue<Edge> pq = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(islandMap[i][j] == 0) continue;
for (int d = 0; d < 2; d++) { // 다리가 중복될 수 있으므로 4방향을 다 볼 필요가 없음
int x = i, y = j;
int dist = 0;
// d 방향으로 쭉 이동하다가 다른 섬을 만나면 다리 연결
while(true){
x += dx[d];
y += dy[d];
// 범위를 벗어나거나 같은 섬이라면 그만 본다
if(!inBound(x, y) || islandMap[x][y] == islandMap[i][j]) break;
if(islandMap[x][y] == 0) dist++;
else if(islandMap[x][y] != islandMap[i][j]){
// 다른 섬을 찾으면 길이가 2 이상인 다리만 연결
if(dist > 1) pq.add(new Edge(islandMap[i][j], islandMap[x][y], dist));
break;
}
}
}
}
}
return pq;
}
private static int findIsland() {
int islandNum = 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(islandMap[i][j] != 1) continue;
checkIsland(i, j, islandNum++);
}
}
return islandNum - 2;
}
private static void checkIsland(int x, int y, int islandNum) {
Queue<Pos> q = new LinkedList<>();
q.add(new Pos(x, y));
while(!q.isEmpty()){
Pos p = q.poll();
if(islandMap[p.x][p.y] == islandNum) continue;
islandMap[p.x][p.y] = islandNum;
for (int d = 0; d < 4; d++) {
int nx = p.x + dx[d];
int ny = p.y + dy[d];
if(!inBound(nx, ny) || islandMap[nx][ny] == 0) continue;
q.add(new Pos(nx, ny));
}
}
}
static boolean inBound(int x, int y){
return !(x < 0 || y < 0 || x >= n || y >= m);
}
static int findRoot(int n){
if(root[n] == n) return n;
return root[n] = findRoot(root[n]);
}
static void union(int r1, int r2){
root[r1] = r2;
}
}
기본적으로는 크루스칼 알고리즘으로 푸는데, 이제 같은 트리라는 것만 확안하는 것이 아니라 한 트리 안에 발전소가 1개만 있어야 한다는 조건이 추가된다. 그래서 union을 할 때에는 루트값을 무조건 발전소가 있는 번호가 저장되도록 설정했고, find로 찾은 루트가 모두 발전소라면 넘어가도록 처리해주었다.
그리고 모든 도시가 하나의 발전소에 연결되기 위해서 필요한 케이블의 개수는 n-k개이다. 설치된 케이블의 개수를 확인하여 n-k가 되면 while문을 종료하도록 했다.
코드
package week7;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class BJ10423 {
static class Edge implements Comparable<Edge> {
int from, to, cost;
public Edge(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return this.cost - o.cost;
}
}
static int[] root;
static ArrayList<Integer> powerPlant;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
// 발전소가 설치된 도시의 번호
powerPlant = new ArrayList<>();
PriorityQueue<Edge> pq = new PriorityQueue<>();
st = new StringTokenizer(br.readLine());
while(st.hasMoreTokens()){
int val = Integer.parseInt(st.nextToken());
powerPlant.add(val);
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
pq.add(new Edge(u, v, w));
}
// 크루스칼 알고리즘
root = new int[n+1];
for (int i = 0; i <= n; i++)
root[i] = i;
int answer = 0;
int cnt = 0;
while(!pq.isEmpty()){
if(cnt == n-k) break;
Edge e = pq.poll();
int r1 = find(e.from);
int r2 = find(e.to);
// 같은 트리 안에 있거나, 둘 다 발전소에 연결되어 있을 경우 넘어감
if(r1 == r2 || (powerPlant.contains(r1) && powerPlant.contains(r2))) continue;
union(r1, r2);
answer += e.cost;
cnt++;
}
System.out.println(answer);
}
static int find(int n){
if(root[n] == n) return n;
return root[n] = find(root[n]);
}
static void union(int r1, int r2){
if(powerPlant.contains(r1)){
int tmp = r1;
r1 = r2;
r2 = tmp;
}
root[r1] = r2;
}
}
테스트 케이스의 개수가 정해져있지 않고 0 0이 들어오면 종료한다는 조건 이외에는, 다른 크루스칼 알고리즘들과 동일하다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class BJ6497 {
static class Edge implements Comparable<Edge> {
int from, to, cost;
public Edge(int from, int to, int cost){
this.from = from;
this.to = to;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return this.cost - o.cost;
}
}
static int[] root;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
StringBuilder sb = new StringBuilder();
while(true){
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
// 테스트 케이스 종료
if(m == 0 && n == 0)
break;
PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
root = new int[m+1];
for (int i = 0; i < m+1; i++)
root[i] = i;
for (int i = 0; i < n; i++){
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int z = Integer.parseInt(st.nextToken());
pq.add(new Edge(x, y, z));
}
int minCost = kruskal(m, pq);
sb.append(minCost).append("\n");
}
System.out.println(sb);
}
private static int kruskal(int m, PriorityQueue<Edge> pq) {
int res = 0;
int cnt = 0;
while(!pq.isEmpty()){
if(cnt == m-1) break;
Edge e = pq.poll();
int r1 = find(e.from);
int r2 = find(e.to);
if(r1 == r2){
res += e.cost;
continue;
}
union(r1, r2);
cnt++;
}
while(!pq.isEmpty()){
Edge e = pq.poll();
res += e.cost;
}
return res;
}
private static void union(int r1, int r2) {
root[r1] = r2;
}
static int find(int n){
if(root[n] == n) return n;
return root[n] = find(root[n]);
}
}
