[BOJ] 백준 1395번 스위치 (Java)

#1395 스위치

난이도 : 플레 3

유형 : 세그먼트 트리 / Lazy propagation

1395번: 스위치

▸ 문제

준규네 집에는 총 N개의 스위치가 있고 이를 편하게 1번부터 N번까지 차례대로 번호를 매겼다. 그리고 준규의 취미는 이 스위치들을 켜고 끄는 것이다.

준규가 하는 스위치를 갖고 노는 일은 크게 두 가지이다. 하나는 A번부터 B번 사이의 스위치 상태를 반전시키는 것이고 다른 하나는 C번부터 D번 사이의 스위치 중 켜져 있는 상태의 스위치의 개수를 세는 것이다.

하지만 준규가 싫증을 느껴 우리가 이 귀찮은 일을 떠맡게 되었고 프로그래밍을 통해 일을 처리하도록 결정하였다.

▸ 입력

첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O가 0이면 Si번 스위치부터 Ti번 스위치까지 스위치 상태를 반전시키는 일이고 1이면 Si번 스위치부터 Ti번 스위치까지 중 켜져 있는 상태의 스위치 개수를 묻는 일이다. 단, 초기에는 모든 스위치의 상태는 꺼져있는 상태로 되어있다.

▸ 출력

입력에서 켜진 스위치 개수에 대한 답을 한 줄에 하나씩 출력한다.

 

문제 풀이  

구간 합과 구간 업데이트를 필요로 하는 느리게 갱신되는 세그먼트 트리 문제이다.  느리게 갱신된다는 말은 굳이 현재 갱신할 필요가 없는 부분들은 따로 보관해놨다가 갱신이 필요할 때 접근하여 한번에 업데이트 시켜준다는 뜻이다. 만약 1-4 구간의 업데이트 후 3-4 구간만 사용한다면 1-2구간은 굳이 갱신해줄 필요가 없으므로 갱신하지 않은 상태로 냅둔다.

 

구간 스위치 상태 반전시키기

스위치는 turn on / off ( 1/ 0)의 두 가지 상태를 지닌다. 구간 단위로 처리할 것이므로 [a, b] 구간의 업데이트가 필요할 때 구간 총 길이에서 현재 켜져있는 스위치를 빼주면 상태 변화가 일어난다.

• [a, b] 스위치 상태 반전 시키기 =  구간 총 길이 - 현재 켜져있는 스위치 갯수
• tree[node] = (e-s+1) - tree[node] 

 

구간 스위치 합 구하기

[a, b] 구간에서 켜져있는 스위치 합은 그냥 기존 구간합과 동일하다. 상태가 1인 스위치의 합을 구해주면 된다.

 

 

느리게 갱신 시키기

lazy update를 시키는 구간은 총 3군데에 필요하다. 

• update쿼리함수가 [s, e]에 접근할 때
• update쿼리에서 update 구간에 속할 때 (l <= s && e <= r)
• pSum쿼리에서 [s, e]에 접근할 때

 

저 위의 세 가지 경우에 도착하게 되면 다음과 같이 로직을 작성해주면된다.

1. 해당 노드 lazy가 등록되어있으면 업데이트해준다. 단, 상태는 2개이기 때문에 홀수인 경우만 업데이트 한다. 짝수인 경우는 원상태로 돌아오기 때문이다  if(lazy[node] % 2 == 1)
2. 리프노드인 경우 물려줌은 패스
3. 리프노드가 아닌 경우 자식 노드들에게 lazy를 물려준다. (나중에 필요하게 될 때가 오면 갱신; 구간 합 구하는 로직)
4. 해당 노드는 이제 업데이트 처리를 해준다. tree[node] = (e-s+1) - tree[node] 
   1. ex) update 1 1 2: 1~2구간에 속하는 스위치 상태를 반전시켜준다. 만약 0개가 켜져있다면 2-0 = 2
5. 업데이트 완료 후 해당 노드 lazy값을 삭제한다. lazy[node] =0;

static void propagte(int s, int e, int node) {
	if(lazy[node] % 2 == 1) {
		if(s != e) {
			lazy[node*2] += lazy[node];
			lazy[node*2+1] += lazy[node];
		}
		tree[node] = (e-s+1) - tree[node];
		lazy[node] = 0;
	}
}

 

 

시뮬레이션

마지막으로 시뮬레이션 과정을 보면 이해가 더 쉬울 것이다. 주어진 예제를 통해 과정을 한번 살펴보자.

 

[1, 2] 스위치 반전

• 1 ~ 2번의 스위치를 반전시켜준다. 2-0 =2
• 4, 5번 노드까지는 굳이 들어갈 필요가 없으므로 lazy상태로 냅둔다.

 

[1, 2] 스위치 반전

 

[2, 4] 스위치 반전

• 2 ~ 4번의 스위치를 반전시켜준다.
• 2번을 갱신시켜줘야하므로 lazy 업데이트를 시켜준다. (1번은 덤으로) 이미 켜져있으므로 1-1 = 0 으로 반전시켜준다.
• 3,4번은 위에 1,2번 업데이트할 때와 마찬가지로 [3,4]구간까지만 업데이트 시켜주고 리프노드들은 lazy상태로 냅둔다.

 

[2, 4] 스위치 반전

 

[2, 3] 구간 합 구하기

• 2 ~ 3번 구간합을 구한다.
• 3번 리프노드에 방문하면서 lazy 업데이트를 갱신한다. (덤으로 4번노드까지)

[2, 3] 구간 합 구하기

 

이런식으로 계속해서 연산을 이뤄나가게 된다.

 

풀이 코드 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	static int[] tree, lazy;
	static int n;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		tree = new int[4*n];
		lazy = new int[4*n];
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int op = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if(op == 0) {
				update(1, n, 1, a, b);
			}else {
				sb.append(pSum(1,n,1,a,b)+"\n");
			}
		}
		System.out.println(sb.toString());
	}
	
	static void propagte(int s, int e, int node) {
		if(lazy[node] % 2 == 1) {
			if(s != e) {
				lazy[node*2] += lazy[node];
				lazy[node*2+1] += lazy[node];
			}
			tree[node] = (e-s+1) - tree[node];
			lazy[node] = 0;
		}
	}
	
	static void update(int s, int e, int node, int l, int r) {
		propagte(s, e, node);
		if(e < l || r < s) return;
		if(l <= s && e <= r) {
			lazy[node] = 1;
			propagte(s, e, node);
			return;
		}
		
		int mid = (s+e)/2;
		update(s, mid, node*2, l, r);
		update(mid+1, e, node*2+1, l, r);
		tree[node] = tree[node*2] + tree[node*2+1];
	}
	
	static int pSum(int s, int e, int node, int l, int r) {
		propagte(s, e, node);
		if(e < l || r< s) return 0;
		if(l <= s && e <= r) {
			return tree[node];
		}
		
		int mid = (s+e)/2;
		return pSum(s, mid, node*2, l, r) + pSum(mid+1, e, node*2+1, l, r); 
	}
}