고양멍멍이

[문제링크]

비슷한 문제

-숨바꼭질

-숨바꼭질2

0. 수빈이의 이동 방법 3가지를 활용해, 동생에게 가장 빠르게 갈 수 있는 경우 찾기

  - 3개의 선택지가 있는 탐색 문제.

  - 어떤 선택지를 먼저 선택하느냐에 따라 해가 나오지 않거나 큰 해가 나오는 경우가 존재하므로 DFS가 아닌 BFS 사용

  - 단, 걷는 방법과 순간이동 방법의 소모 시간이 다르므로, BFS의 형식만 따를 뿐 이론적으로 BFS로 작동하지 않는다

  - ex) +1+1+1+1과 *2 *2 *2 *2는 각각 4번의 이동을 하지만, 소모 시간은 4초 / 0초로 다름

  - 전체 경우의 수를 탐색한다

1. 수빈이의 시작지점 N에서 BFS방식으로 +1, -1, *2 지점을 큐에 넣으며 진행한다

2. 수빈이가 어떤 칸 X에 W초를 걸려 도달했는데, 이미 해당 칸에 W보다 적은 시간으로 도달한 기록이 있다면, 더이상 탐색하는것은 의미가 없다.

  - 어떤 칸 X에 몇초만에 도달하였는지를 num 배열에 저장하여, 현재의 시간이 더 작을때에만 진행하도록 한다

  - 숨바꼭질 기본 문제와는 달리, 순간이동의 소모 시간이 0이므로, num[X]가 0인지 아닌지만으로는 판단할 수 없다

3. 수빈이의 현재 위치가 동생의 위치보다 크다면, +1 *2 연산을 진행할 필요는 없다

  - 마찬가지로, 수빈이의 현재 위치가 동생의 위치보다 작다면, -1 연산을 진행할 필요는 없다

4. 정리하자면,

  - 현재 좌표 X가 동생의 좌표 K보다 작으며, X+1 좌표의 이전 접근 시간이 현재 시간보다 클때만 진행+갱신

  - 현재 좌표 X가 동생의 좌표 K보다 작으며, X*2 좌표의 이전 접근 시간이 현재 시간보다 클때만 진행+갱신

  - 현재 좌표 X가 동생의 좌표 K보다 크며, X-1 좌표의 이전 접근 시간이 현재 시간보다 클때만 진행+갱신하며,

  - K좌표에 도달하는 순간 연산 횟수를 출력, 종료한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int len=100001;
		int[] num = new int[len*2];
		int[] way = new int[len*2];
		Arrays.fill(num, Integer.MAX_VALUE);
		way[N]=1;
		num[N]=0;
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(N);
		
		while(!q.isEmpty()) {
			int temp = q.poll();
			if(temp < K && num[temp*2]>num[temp]) {
				way[temp*2]+=way[temp];
				if(num[temp*2]!=num[temp]+1)q.offer(temp*2);
				num[temp*2]=num[temp];
			}
			if(temp < K && num[temp+1]>num[temp]) {
				way[temp+1]+=way[temp];
				if(num[temp+1]!=num[temp]+1)q.offer(temp+1);
				num[temp+1]=num[temp]+1;
			}
			if(temp-1 >= 0 && num[temp-1]>num[temp]) {
				way[temp-1]+=way[temp];
				if(num[temp-1]!=num[temp]+1)q.offer(temp-1);
				num[temp-1]=num[temp]+1;
			}
		}
		System.out.println(num[K]);
	}
}

[문제링크]

비슷한 문제

-숨바꼭질

0. 수빈이의 이동 방법 3가지를 활용해, 동생에게 가장 빠르게 갈 수 있는 경우 + 그 갯수 찾기

  - 3개의 선택지가 있는 탐색 문제.

  - 어떤 선택지를 먼저 선택하느냐에 따라 해가 나오지 않거나 큰 해가 나오는 경우가 존재하므로 DFS가 아닌 BFS 사용

1. 수빈이의 시작지점 N에서 BFS방식으로 +1, -1, *2 지점을 큐에 넣으며 진행한다

2. 수빈이가 어떤 칸 X에 W초를 거쳐 도달했는데, 이미 해당 칸에 W보다 적은 시간으로 도달한 기록이 있다면, 더이상 탐색하는것은 의미가 없다.

  - 하지만 같은 칸에 동일하게 W초만에 도달했을 경우는 고려해야한다 (가짓수를 구하기 위해)

  - way배열을 두어 W초를 사용해 X번 칸에 도달할 수 있는 가짓수를 저장한다.

3. 수빈이의 현재 위치가 동생의 위치보다 크다면, 반드시 작아져야하므로 +1 *2 연산을 진행할 필요 없다

  - 마찬가지로, 수빈이의 현재 위치가 동생의 위치보다 작다면, 반드시 커져야하므로 -1 연산을 진행할 필요 없다

4. 정리하자면,

  - 현재 좌표 X가 동생의 좌표 K보다 작으며, X+1 좌표에 진행해본 적 없거나 || 현재 이동수 W와 같을때만 진행

  - 현재 좌표 X가 동생의 좌표 K보다 작으며, X*2 좌표에 진행해본적이 없거나 || 현재 이동수 W와 같을때만 진행

  - 현재 좌표 X가 동생의 좌표 K보다 크며, X-1 좌표에 진행해본적이 없거나 || 현재 이동수 W와 같을때만 진행하며,

  - K좌표에 도달하는 순간 연산 횟수를 출력, 종료한다

  - 시작할 때 큐의 크기 = W단계에서 연산해야할 크기이므로, 큐의 크기만큼 반복할때마다 1씩 증가하는 act 변수를 두어, 이동 수를 관리한다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int len=100001;
		int[] num = new int[len*2];
		int[] way = new int[len*2];
		way[N]=1;
		num[N]=1;
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(N);
		
		int act=1;
		while(num[K]==0) {
			act++;
			int qlen=q.size();
			for (int i = 0; i < qlen; i++) {
				int temp = q.poll();
				if(temp < K) {
					if(num[temp*2]==0) {
						q.offer(temp*2);
						num[temp*2]=act;					
					}
					if(num[temp*2]==act)way[temp*2]+=way[temp];
				}
				if(temp < K) {
					if(num[temp+1]==0) {
						q.offer(temp+1);
						num[temp+1]=act;						
					}
					if(num[temp+1]==act)way[temp+1]+=way[temp];
				}
				if(temp-1 >= 0) {
					if(num[temp-1]==0) {
						q.offer(temp-1);
						num[temp-1]=act;						
					}
					if(num[temp-1]==act)way[temp-1]+=way[temp];
				}
			}
		}
		System.out.println(num[K]-1);
		System.out.println(way[K]);
	}
}

[문제링크]

0. j ~ j+i 까지의 수가 팰린드롬 수가 되려면

  - j, j+1번 자리의 수가 같아야하며

  - j+1 ~ j+i-1 까지의 수가 팰린드롬 수여야 한다

1. 1, 2자리 수에 대해 팰린드롬 수 여부를 계산한다

  - 1자리의 수는 전부 다 팰린드롬 수

  - 두 자리의 수가 연속이라면 팰린드롬 수

2. isP[x][y] 배열은 y번째 수부터, x개의 수를 고려했을때 해당 수가 팰린드롬인지 여부를 판단한다

  - isP[10][5] - 5~14의 수가 팰린드롬인지 정보 저장

3. 3자리부터 n자리까지 모든 가능한 경우에 대해 팰린드롬 수 여부를 검사한다

  - isP[i-2][j+1] : j+1 ~ j+i-1까지의 팰린드롬 여부

4. m개의 입력을 처리하며, 미리 구성된 isP 정보에 따라 1/0 출력 결정

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = pint(br.readLine());
		int[] num = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			num[i]=pint(st.nextToken());
		}
		//2.
		boolean[][]isP = new boolean[N][N];
        
		//1.
		Arrays.fill(isP[0], true);
		for (int i = 0; i < N-1; i++) {
			if(num[i]==num[i+1])isP[1][i]=true;
		}
        
		//3.
		for (int i = 2; i < N; i++) {
			for (int j = 0; j < N-i; j++) {
				if(num[j]==num[j+i]) {
					if(isP[i-2][j+1]) {
						isP[i][j]=true;
					}
				}
			}
		}
        
		//4.
		int m = pint(br.readLine());
		for (int i = 0; i < m; i++) {
			st=new StringTokenizer(br.readLine());
			int s = pint(st.nextToken()), e=pint(st.nextToken());
			sb.append(isP[e-s][s-1]?1:0).append("\n");
		}
		System.out.println(sb);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. A칸에서 이동해 B칸으로 갈 경우, A와 B는 같은 집합에 속한다

  - 이러한 이동-집합에 대해, 각 집합당 1개의 SAFE-ZONE이 필요하게 된다

  - disjoint-set으로 집합 관리

1. n*m개의 각 칸을 set으로 만들고, set의 갯수 또한 n*m으로 초기화한다

2. 모든 칸을 순회하며 각 칸의 이동에 따라 도착지점의 set과 결합한다

3. 최종적으로 남아있는 set의 갯수가 필요한 SAFE-ZONE의 수가 된다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = pint(st.nextToken());
		m = pint(st.nextToken());
        
		init();
		
		for (int i = 0; i < n; i++) {
			String s =br.readLine();
			for (int j = 0; j < m; j++) {
				switch(s.charAt(j)) {
				case 'U':
					union(i*m+j, (i-1)*m+j);
					break;
				case 'D':
					union(i*m+j, (i+1)*m+j);
					break;
				case 'L':
					union(i*m+j, i*m+j-1);
					break;
				case 'R':
					union(i*m+j, i*m+j+1);
					break;
				default:
					break;
				}
			}
		}
		
		System.out.println(cntSet);
		
	}
	static int n,m;
	static int[][]parent;
	static int cntSet;
	
	static void init() {
		parent = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				parent[i][j]=m*i+j;
			}
		}
		cntSet=n*m;
	}
	
	static int find(int x) {
		if(parent[x/m][x%m]!=x)return parent[x/m][x%m]=find(parent[x/m][x%m]);
		return x;
	}
	
	static void union(int x, int y) {
		int rx = find(x), ry=find(y);
		if(rx!=ry) {
			parent[rx/m][rx%m]=ry;
			cntSet--;
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. treeNode 자료구조는 부모 index, 자기 value, 자식 index의 List로 구성됨

  - treeNode의 배열로서 tree를 표현한다

1. 문제의 입력은 0-base지만, 편의상 1-base로 변경. 0은 가상의 head node로서 사용한다

2. 입력을 받으며 자신의 parent에 등록 + parent의 child에 등록해 tree 완성

3. 0번을 parent로 가지는, tree의 root노드로부터 bfs 탐색한다

  - child가 없는 node는 leaf이므로 센다

4. 탐색 노드가 삭제할 node일 경우, 해당 노드로부턴 더 이상 탐색하지 않는다

  - 삭제 node의 parent의 child 갯수가 1개라면 : 이 node의 삭제로 parent노드가 leaf가 되었으니 센다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int root=0, deadNode=0, cntLeaf=0;
		int N = pint(br.readLine());
		treeNode[]tree = new treeNode[N+1];
		for (int i = 0; i <= N; i++) {
			tree[i]=new treeNode();
		}
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			int p = pint(st.nextToken())+1;
			tree[i].parents=p;
			tree[i].value=i;
			tree[p].children.add(i);
			if(p==0)root=i;
		}
		deadNode=pint(br.readLine())+1;
		
		Queue<Integer>qu = new LinkedList<>();
		qu.offer(root);
		cntLeaf=0;
		while(!qu.isEmpty()) {
			int node=qu.poll();
			if(tree[node].value==deadNode) {
				if(tree[node].parents!=0 && tree[ tree[node].parents ].children.size()==1) {
					cntLeaf++;
				}
				continue;
			}
			
			if(tree[node].children.isEmpty()) {
				cntLeaf++;
			}
			else {
				for (int i = 0; i < tree[node].children.size(); i++) {
					int next=tree[node].children.get(i);
					qu.offer(next);
				}
			}
		}
		System.out.println(cntLeaf);
	}
	static class treeNode{
		int parents;
		int value;
		ArrayList<Integer>children=new ArrayList<>();
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 사방 처리를 위해 외곽을 1로 감쌌다

1. 전체를 탐색하면서 0, 빈공간을 만날 경우 BFS 진행

  - BFS에서 거쳐가는 모든 칸을 index로 칠해 재탐색 방지 + 추후 이용

  - BFS의 결과로 반환된 size를 ArrayList에 저장한다

  - ( 0은 빈칸, 1은 벽이므로 area index는 2부터 시작, index 유지를 위해 0 2개 삽입)

2. 전체를 탐색하면서 벽을 만날 경우 4방향에 대해

  - 1이 아니면 빈 공간이 index로 칠해진 것. 해당 index의 size를 ArrayList로부터 가져와 누적한다.

  - 1이면 벽, 무시한다

3. 각 방향의 area index가 같다면, 두번 더해선 안된다.

  - 4개의 값이므로, 각각 이전 값들과 다를 경우에만 누적한다 ( 가독성, 확장성은 좋지 않지만, 성능 효율적 )

  - set에 다 던져넣고 하나씩 꺼내며 쓴다 ( 가독성, 확장성은 좋지만, 성능 비효율적)

4. 출력할 때 println등을 이용하면 최악 1000*1000번 출력하게되므로, buffer 이용이 필수적이다

+ 4번 print구간은 3번 반복문에 그대로 삽입할 수 있다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		
		map=new int[n+2][m+2];
		int[][]ansMap=new int[n+2][m+2];
		//외곽 padding
		for (int i = 0; i < n+2; i++) {
			map[i][0]=1;map[i][m+1]=1;
		}
		for (int i = 0; i < m+2; i++) {
			map[0][i]=1;map[n+1][i]=1;
		}
		// 1. input
		for (int i = 1; i <= n; i++) {
			String s = br.readLine();
			for (int j = 1; j <= m; j++) {
				map[i][j]=s.charAt(j-1)-'0';
			}
		}
		//2. get size by bfs for each area + tagging
		ArrayList<Integer>area=new ArrayList<>();
		area.add(0);area.add(0);
		int idx=2;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if(map[i][j]==0) {
					int size=search(idx++, i, j);
					area.add(size);
				}
			}
		}
		//3. check four-dir of each wall + add if area
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if(map[i][j]==1) {
					ansMap[i][j]+=1;
					if(map[i+1][j]!=1)
						ansMap[i][j]+=area.get(map[i+1][j]);
					if(map[i][j+1]!=1 && map[i+1][j]!=map[i][j+1])
						ansMap[i][j]+=area.get(map[i][j+1]);
					if(map[i-1][j]!=1&& map[i+1][j]!=map[i-1][j] && map[i-1][j]!=map[i][j+1])
						ansMap[i][j]+=area.get(map[i-1][j]);
					if(map[i][j-1]!=1 && map[i][j-1]!=map[i+1][j]&& map[i][j-1]!=map[i][j+1] && map[i][j-1]!=map[i-1][j])
						ansMap[i][j]+=area.get(map[i][j-1]);
				}
			}
		}
		//4.print
		for (int i = 1; i < n+1; i++) {
			for (int j = 1; j < m+1; j++)sb.append(ansMap[i][j]%10);
			sb.append("\n");
		}System.out.println(sb);
	}
	static int[][]map;
	static int search(int idx, int x, int y) {
		int size=1;
		map[x][y]=idx;
		if(map[x+1][y]==0)size+=search(idx,x+1,y);
		if(map[x-1][y]==0)size+=search(idx,x-1,y);
		if(map[x][y+1]==0)size+=search(idx,x,y+1);
		if(map[x][y-1]==0)size+=search(idx,x,y-1);
		return size;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. disjoint set 문제

1. A에서 B로 선분을 그으려 할 때, 이미 A와 B가 같은 집합에 속한다면 사이클이 생성된다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		
		init(n);
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = pint(st.nextToken());
			int y = pint(st.nextToken());
			if(!union(x,y)) {
				System.out.println(i+1);
				break;
			}
			else if(i==m-1) {
				System.out.println(0);
			}
		}
		
	}
	static int[] parents;
	
	static void init(int n) {
		parents=new int[n];
		for (int i = 0; i < n; i++) {
			parents[i]=i;
		}
	}
	
	static int find(int n) {
		if(parents[n]!=n)return parents[n]=find(parents[n]);
		return n;
	}
	
	static boolean union(int x, int y) {
		int px=find(x), py=find(y);
		if(px==py)return false;
		
		parents[px]=py;
		return true;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

[문제링크]

0. 알파벳은 26자이므로, 32bit int를 사용해 bit-masking으로 등장 정보를 저장한다

1. chk변수에는 모든 알파벳 정보를 저장해, 등장하는 알파벳들에 대해서만 검사하도록 한다

2. a,n,t,i,c 5자는 반드시 등장하므로, 기본적으로 지워두고 시작한다

3. m이 5보다 작으면, 위 5자를 지울수 없으므로 즉시 실패, 아니라면 남은 알파벳의 모든 조합을 구한다

4. 모든 가능한 조합에 대해 알파벳을 지워보면, 모든 알파벳이 가르쳐진 단어는 그 값이 0이된다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	
	static int n,m,chk,max;
	static int[]word;
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = pint(st.nextToken());
		m = pint(st.nextToken());
		word = new int[n];
		//기본으로 지워줘야하는 단어들
		int[]base=new int[] { 1<<'a'-'a', 1<<'n'-'a', 1<<'t'-'a', 1<<'i'-'a', 1<<'c'-'a'};
		
		//bit로 저장
		chk=0;
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < s.length(); j++) {
				word[i] = word[i] | 1<<(s.charAt(j)-'a');
				chk=chk | 1<<(s.charAt(j)-'a');
			}
		}
		
		//기본 5개 삭제
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 5; j++) {
				word[i] = word[i] & ~base[j];
				chk = chk & ~base[j];
			}
		}
		m-=5;
		
		max=0;
		if(m>=0)combi(0,0);
		System.out.println(max);
	}
	
	static void combi(int cnt, int prev) {
		if(cnt>=m || chk==0) {
        	//n개의 단어를 다 가르쳤을때
			int readCnt=0;
			for (int i = 0; i < n; i++) {
				if(word[i]==0)readCnt++;
			}
			max=Math.max(max, readCnt);
			return;
		}
		int[]temp = word.clone();
		int tempchk=chk;
		
		for (int i = prev; i < 26; i++) {
			if( (chk & 1<<i) != 0 ) {
				word=temp.clone();
				chk=tempchk;
				
				chk = chk & (~(1<<i));
				for (int j = 0; j < n; j++) {
					word[j] = word[j] & (~(1<<i));
				}

				combi(cnt+1, i+1);
			}
		}
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}