문제풀이

두가지 접근방법

1. DFS 를 이용한 전체 탐색

 - 처음에 시도했던 방법이다.  메모리 초과가 나와서 역시나했나다..

   그 이유는 최대 10^5 개의 숫자를 DFS로 탐색하려면 엄청난 메모리가 사용될거라 생각했다.

   이 방법이 틀린줄 알면서 풀어본 이유는 대부분의 코딩테스트는 정수론 문제는 거의 출제하지 않는것 같기 때문이다.

2. 정수론을 이용한 정렬

 - 문제에서 주어지는 30 이란 숫자에서 생각해낸 방법이다.

   다른분들의 풀이를 보면서 참고하였다.

1) 우선 3의 배수의 특징은 각 자리수의 합이 3의 배수라는 점이 있다.

2) 우리는 30의 배수를 찾아야 하므로 입력받은 숫자를 정렬했을때 처음에 0이 오면 된다.

3) 두 가지 조건을 이용하여  30의 배수인지 아닌지 찾았다.

소스코드1

소스코드2

https://www.acmicpc.net/problem/10610

문제풀이

1. 알파벳이 나왔는지 확인할 수 있는 배열을 만들어서 해당 문자를 아직 방문하지 않았을 경우에만 방문하는

방법을 사용한다.

2. dfs 매개변수로 현재까지 나온 문자열을 전달하여 이 문자열에 포함되어 있지않으면 다음 문자를 추가해 주는 방식

이때 s.contains(Chracter.toString(arr[ny][nx]))  이러한 방법을 이용하는데 이 contains 라는 메소드가 배열 길이 만큼 시간이 걸린다. 이걸 dfs로 돌리면 시간이 매우 오래 걸리지만 통과는 하는 듯 싶다.

두가지 방법을 모두 한번씩 확인해보고 왜 1번 방법이 더 빠른지 생각해보면 좋을듯 싶다.

소스코드1

소스코드2

연구소

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0 1 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2 1 0 1 0 1 2 2 0 1 1 0 1 2 2 0 1 0 0 0 1 2 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

문제풀이

1. 이차원 배열에서 0인 위치( 빈칸 ) 세 곳을 벽(1)로 만든다.

2. 해당 배열을 복사한 후 복사한 배열에서 바이러스를 퍼지게 한 후 남은 빈칸의 개수의 최대값을 구한다.

우선 빈칸 3개의 경우 모두를 뽑을 수 있어야 한다.

이러한 경우 조합 알고리즘을 이용한다.

2021.09.24 - [Programming/Algorithm] - 순열과 조합

다음 순열과 조합 관련 게시물을 참고하여 Combination 방법에 대해서 참고하자.

세개의 벽을 골랐으면 이제 바이러스를 퍼뜨릴 차례이다.

이때에는 BFS, DFS 원하는 방법을 사용하면 된다.

나 같은 경우는 BFS가 좀 더 직관적으로 이해하기 편해서 BFS를 이용하였다.

바이러스와 인접한 위치에 0(빈칸)이 있으면 바이러스로 바꿔주고 해당위치를 Queue에 넣어 반복 작업을 한다.

소스코드

import java.util.*;
import java.io.*;
class Main{
	static int n, m;
	static int[][] map;
	static boolean[][] visited;
	static boolean[] selected;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	static List<Pos> empty = new ArrayList<>();
	static int max;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][m];
		selected = new boolean[n*m];
		for(int i=0;i<n;i++)
		{
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<m;j++)
			{
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 0)
					empty.add(new Pos(i,j));
			}
		}
		dfs(0,0);
		
		System.out.println(max);
		
	}
	
	//조합
	static void dfs(int depth, int idx)
	{
		if(depth == 3)
		{
			int[][] copy_map = new int[n][m];
			for(int i=0;i<n;i++)
			{
				for(int j=0;j<m;j++)
				{
					copy_map[i][j] = map[i][j];
				}
			}
			int cnt = 0;
			for(int i=0;i<empty.size();i++)
			{
				if(cnt == 3) break;
				if(selected[i])
				{
					copy_map[empty.get(i).y][empty.get(i).x] = 1;
					cnt++;
				}
			}
			int sum = virus(copy_map);
			max = Math.max(sum, max);
			return;
		}
		for(int i=idx;i<empty.size();i++)
		{
			if(selected[i])continue;
			selected[i] = true;
			dfs(depth+1, i);
			selected[i] = false;
		}
	}
	static int virus(int[][] map2)
	{
		Queue<Pos> q = new LinkedList<>();
		visited = new boolean[n][m];
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(map2[i][j] == 2)
				{
					q.add(new Pos(i,j));
					visited[i][j] = true;
				}
			}
		}
		
		//바이러스(2) 와 인접한 칸이 빈칸일 경우
		//바이러스 퍼뜨리기.
		while(!q.isEmpty())
		{
			Pos now = q.poll();
			for(int i=0;i<4;i++)
			{
				int ny = now.y + dy[i];
				int nx = now.x + dx[i];
				if(ny >=0 && nx >=0 && ny <n && nx < m)
				{
					if(!visited[ny][nx] && map2[ny][nx] == 0)
					{
						q.add(new Pos(ny,nx));
						visited[ny][nx] = true;
						map2[ny][nx] = 2;
					}
				}
			}
		}
		
		//바이러스를 퍼뜨리고 난 후
		//0 의 개수 카운딩
		int empty = 0;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(map2[i][j] == 0)
					empty++;
			}
		}
		return empty;
	}
}
class Pos{
	int y,x;
	public Pos(int y, int x)
	{
		this.y = y;
		this.x = x;
	}
}

바이러스

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

이 문제의 경우에는 내가 아는 해결방법은 세가지가 있다.

1. DFS 깊이 우선 탐색

2. BFS 너비 우선 탐색

3. Union Find 

세가지 풀이 방법에 대해 주석과 함께 소스코드를 올려보았다.

1. DFS

import java.util.*;
import java.io.*;
class Main{
	static int n,m;
	static ArrayList<Integer>[] tree;
	static boolean[] visited;
	static int ans;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		visited = new boolean[n+1];
		tree = new ArrayList[n+1];
		for(int i=1;i<=n;i++)
			tree[i] = new ArrayList<>();
		
		for(int i=0;i<m;i++)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			tree[a].add(b);
			tree[b].add(a);
		}
		
		dfs(1);
        //문제에서는 1 때문에 감염된 노드의 수를 물어봤으므로 감염된 전체 노드의 개수에서 1을
        //빼준다.
		System.out.println(ans-1);
	}
	public static void dfs(int now)
	{
        //방문했으면 종료
		if(visited[now]) return;
		visited[now] = true;
		ans++;
		for(int next : tree[now])
		{
        	//연결된 노드 중에 방문하지 않았으면 방문
			if(!visited[next])
			{
				dfs(next);
			}
		}
	}
}

2. BFS

import java.util.*;
import java.io.*;
class Main{
	static int n,m;
	//입력 배열
	static ArrayList<Integer>[] tree;
	static boolean[] visited;
	static int ans;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		visited = new boolean[n+1];
		tree = new ArrayList[n+1];
		for(int i=1;i<=n;i++)
			tree[i] = new ArrayList<>();
		
		for(int i=0;i<m;i++)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			tree[a].add(b);
			tree[b].add(a);
		}
		
		bfs(1);
		System.out.println(ans);
	}
	public static void bfs(int start)
	{
		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		visited[start] = true;
		while(!q.isEmpty())
		{
			int now = q.poll();
			for(int next : tree[now])
			{
				if(!visited[next])
				{
					visited[next] = true;
					q.add(next);
					ans++;
				}
			}
		}
	}
}

3. Union-Find

import java.util.*;
import java.io.*;
class Main{
	static int n,m;
	static int[] parent;
	static int ans;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		parent = new int[n+1];
		for(int i=1;i<=n;i++)
		{
			parent[i] = i;
		}
		
		for(int i=0;i<m;i++)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			union(a,b);
		}
		for(int i=1;i<=n;i++)
		{
			if(find(i) == 1)
				ans++;
		}
		System.out.print(ans-1);
	}
	
	public static int find(int x)
	{
		if(parent[x] == x) return x;
		return parent[x] = find(parent[x]);
	}
	
	public static void union(int a,int b)
	{
		a = find(a);
		b = find(b);
		if(b>a)parent[b] = a;
		else parent[a] = b;
	}
}

DFS와 BFS 

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

이 문제는 DFS와 BFS를 사용할 수 있는지 확인하는 문제입니다.

//문제에서 숫자의 범위가 1부터 시작해서 체크 배열을 n+1로 설정

boolean[] visited = new boolean[n+1];

// list 배열의 의미는 list[i] : i 와 연결된 모든 노드

List<Integer>[] list

import java.util.*;
import java.io.*;
class Main{
	static int n, m, start;
	static boolean[] visited;
	static List<Integer>[] list;
	static List<Integer> dfs_result = new ArrayList<>();
	static StringBuilder sb = new StringBuilder();
	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());
		m = Integer.parseInt(st.nextToken());
		start = Integer.parseInt(st.nextToken());

		list = new ArrayList[n+1];
		for(int i=1;i<=n;i++)
		{
			list[i] = new ArrayList<>();
		}
		
		for(int i=0;i<m;i++)
		{
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			list[a].add(b);
			list[b].add(a);
		}
		for(int i=1;i<=n;i++)
			Collections.sort(list[i]);
		
		visited = new boolean[n+1];
		dfs(start);
		sb.append('\n');
		visited = new boolean[n+1];
		bfs(start);
		
		System.out.println(sb);
	}
	
	static void dfs(int now)
	{
		if(visited[now]) return;
		visited[now] = true;
		sb.append(now).append(" ");
		for(int next : list[now])
		{
			if(!visited[next])
				dfs(next);
		}
	}
	
	static void bfs(int start)
	{
		Queue<Integer> q = new LinkedList<>();
		q.add(start);
		visited[start] = true;
		
		while(!q.isEmpty())
		{
			int now = q.poll();
			sb.append(now).append(" ");
			for(int next : list[now])
			{
				if(!visited[next])
				{
					visited[next] = true;
					q.add(next);
				}
			}
		}
	}
}

문제 설명

IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다.
이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 같은 방식으로 결정하려고 합니다.
해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산문자(+, -, *) 만으로 이루어진 연산 수식이 전달되며, 참가자의 미션은 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다.
단, 연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없어야 합니다. 즉, + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,-처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다. 수식에 포함된 연산자가 2개라면 정의할 수 있는 연산자 우선순위 조합은 2! = 2가지이며, 연산자가 3개라면 3! = 6가지 조합이 가능합니다.
만약 계산된 결과가 음수라면 해당 숫자의 절댓값으로 변환하여 제출하며 제출한 숫자가 가장 큰 참가자를 우승자로 선정하며, 우승자가 제출한 숫자를 우승상금으로 지급하게 됩니다.

예를 들어, 참가자 중 네오가 아래와 같은 수식을 전달받았다고 가정합니다.

"100-200*300-500+20"

일반적으로 수학 및 전산학에서 약속된 연산자 우선순위에 따르면 더하기와 빼기는 서로 동등하며 곱하기는 더하기, 빼기에 비해 우선순위가 높아 * > +,- 로 우선순위가 정의되어 있습니다.
대회 규칙에 따라 + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,- 처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다.
수식에 연산자가 3개 주어졌으므로 가능한 연산자 우선순위 조합은 3! = 6가지이며, 그 중 + > - > * 로 연산자 우선순위를 정한다면 결괏값은 22,000원이 됩니다.
반면에 * > + > - 로 연산자 우선순위를 정한다면 수식의 결괏값은 -60,420 이지만, 규칙에 따라 우승 시 상금은 절댓값인 60,420원이 됩니다.

참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• expression은 길이가 3 이상 100 이하인 문자열입니다.
• expression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(+, -, *) 만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연산식은 입력으로 주어지지 않습니다.
  • 즉, "402+-561*"처럼 잘못된 수식은 올바른 중위표기법이 아니므로 주어지지 않습니다.
• expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다.
  • 즉, "100-2145*458+12"처럼 999를 초과하는 피연산자가 포함된 수식은 입력으로 주어지지 않습니다.
  • "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.
• expression은 적어도 1개 이상의 연산자를 포함하고 있습니다.
• 연산자 우선순위를 어떻게 적용하더라도, expression의 중간 계산값과 최종 결괏값은 절댓값이 2^63 - 1 이하가 되도록 입력이 주어집니다.
• 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.

입출력

문제 풀이

이 문제는 연산자의 우선순위를 재설정하여 연산 결과의 최대값을 구하는 문제이다.

그러면 풀이과정으로

1. 연산자의 우선순위 재설정

-> dfs를 활용하여 모든 경우의 수에 대해 연산 진행

2. 연산 결과의 최대값 구하기

-> 연산 결과는 절대값으로 계산!

3. 연산 결과의 범위

-> 연산결과는 최대 2^63 -1 까지다. 이 말은 c++에서 long 의 범위를 의미하는것으로 보인다.

    난 여유있게 long long으로 계산함

4. 사전작업

-> expression을 숫자 백터와 연산자 백터에 따로 담아 두었다.

(연산자 백터는 항상 숫자 백터 크기보다 1개 작다는것을 주의하자)

-> 연산자 백터에서 중복된 연산자를 제외 한후 dfs를 돌려서 순열을 만들어 모든 우선순위를 구한다.

5. 계산하기

-> 연산자 순서대로 계산 후, 처음에 만들었던 숫자백터와 연산자 백터의 크기를 줄여가며 진행한다.

    숫자 백터의 크기가 1 일때 더이상 연산할것이 없으므로 answer 와 절대값 크기비교를 하며 

    모든 경우의 수를 구해본다.

소스 코드

#include <vector>
#include <string>
#include <algorithm>
using namespace std;
bool selected[3];
vector<char> oper3;
void cal(char operation, vector<char>& oper, vector<long long>& numbers, long long& sum)
{
    auto it = find(oper.begin(), oper.end(), operation);
    while(it != oper.end())
    {
        int idx = it - oper.begin();
        if(operation == '*')
        {
            numbers[idx] = numbers[idx] * numbers[idx+1];
        }
        else if(operation == '+')
        {
            numbers[idx] = numbers[idx] + numbers[idx+1];
        }
        else
        {
            numbers[idx] = numbers[idx] - numbers[idx+1];
        }
        numbers.erase(numbers.begin() + idx+1);
        oper.erase(oper.begin() + idx);
        it = find(it, oper.end(), operation);
    }
    if(numbers.size() == 1)
    {
        sum = abs(numbers[0]);
    }
    return;
}
void dfs(int depth, vector<char> oper, vector<char> oper2, vector<int> nums, long long& answer)
{
    if(depth == oper2.size())
    {
        long long sum = 0;
        vector<long long> numbers;
        for(auto a : nums)
            numbers.push_back(a);
        for(int i=0;i<oper3.size();i++)
        {
            cal(oper3[i], oper, numbers, sum);
        }
        answer = max(sum, answer);
        return;
    }
    for(int i=0;i<oper2.size();i++)
    {
        if(selected[i])continue;
        selected[i] = true;
        oper3.push_back(oper2[i]);
        dfs(depth+1, oper, oper2, nums, answer);
        oper3.pop_back();
        selected[i] = false;
    }
}
long long solution(string expression)
{
    long long answer = 0;
    vector<int> nums;
    vector<char> oper;
    string ttmp="";
    for(int i=0;i<expression.size();i++)
    {
        if(expression[i] >='0' && expression[i] <= '9')
        {
            ttmp+= expression[i];
        }
        else
        {
            oper.push_back(expression[i]);
            nums.push_back(stoi(ttmp));
            ttmp="";
        }
    }
    nums.push_back(stoi(ttmp));

    vector<char> oper2;
    for(int i=0;i<oper.size();i++)
    {
        if(find(oper2.begin(), oper2.end(), oper[i]) == oper2.end())
        {
            oper2.push_back(oper[i]);
        }
    }

    dfs(0, oper, oper2, nums, answer);
    return answer;
}

문제 설명

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.         

5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

• places의 행 길이(대기실 개수) = 5
  • places의 각 행은 하나의 대기실 구조를 나타냅니다.
• places의 열 길이(대기실 세로 길이) = 5
• places의 원소는 P,O,X로 이루어진 문자열입니다.
  • places 원소의 길이(대기실 가로 길이) = 5
  • P는 응시자가 앉아있는 자리를 의미합니다.
  • O는 빈 테이블을 의미합니다.
  • X는 파티션을 의미합니다.
• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
• return 값 형식
  • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
  • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
  • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

입출력

방향 배열을 설정하여 해당 좌표가 범위를 벗어나지않고 'P'일때 기준으로

위와 같은경우와

다음과 책상을 기준으로 한칸 떨어져있을 경우를 확인하며 배열을 탐색해 보았다.

Version2

처음 이 문제를 풀때는 위와같이 경우의 수를 나누어 코딩을 하였다.

이번엔 자바를 이용해서 문제를 풀다가 다른 분의 코드를 보니 다음과같이 해결하였다.

(y,x) 가 'P' 일때를 보면 거리가 2인것 1인것이 보인다. 다아아몬드 모양인게 모양이 규칙성이 보인다.

-> dfs, bfs가 가능하다고 판단. 페이지 맨 아래 dfs,bfs를 사용한 코드가 있다.

소스 코드

#include <vector>
#include <string>
using namespace std;
int dx1[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int dy1[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy2[4] = { 0, -2, 0, 2 };
int dx2[4] = { -2,0,2,0 };
int dy3[4] = { 0, -1, 0, 1 };
int dx3[4] = { -1,0,1,0 };
int distance(int y1, int x1, int y2, int x2)
{
	return abs(y1 - y2) + abs(x1 - x2);
}
bool solve(vector<string> room)
{
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			if (room[i][j] == 'P')
			{
				for (int k = 0; k < 8; k++)
				{
					int ny = i + dy1[k];
					int nx = j + dx1[k];
					if (ny >= 0 && nx >= 0 && ny < 5 && nx < 5)
					{
						if (room[ny][nx] == 'P')
						{
							if (distance(i, j, ny, nx) == 2)
							{
								//왼위
								if (ny == i - 1 && nx == j - 1)
								{
									if (room[i][nx] != 'X' || room[ny][j] != 'X')
										return false;
								}
								//오위
								else if (ny == i - 1 && nx == j + 1)
								{
									if (room[i][nx] != 'X' || room[ny][j] != 'X')
										return false;
								}
								//왼아
								else if (ny == i + 1 && nx == j - 1)
								{
									if (room[i][nx] != 'X' || room[ny][j] != 'X')
										return false;
								}
								//오아
								else if (ny == i + 1 && nx == j + 1)
								{
									if (room[i][nx] != 'X' || room[ny][j] != 'X')
										return false;
								}
							}
							else
								return false;
						}
					}
				}
				for (int k = 0; k < 4; k++)
				{
					int ny = i + dy2[k]; int ty = i + dy3[k];
					int nx = j + dx2[k]; int tx = j + dx3[k];
					if (ny >= 0 && nx >= 0 && ny < 5 && nx < 5)
					{
						if (room[ny][nx] == 'P')
						{
							if (room[ty][tx] == 'O')
							{
								return false;
							}
						}
					}
				}
			}
		}
	}
	return true;
}
vector<int> solution(vector<vector<string>> places)
{
	vector<int> answer;
	for (int i = 0; i < 5; i++)
	{
		if (solve(places[i]))
		{
			answer.push_back(1);
		}
		else
			answer.push_back(0);
	}

	return answer;
}

///DFS
class Solution
{
    int[] ans;
    boolean[][] visited;
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    public int[] solution(String[][] places)
    {
        ans = new int[places.length];
        for(int i=0;i<places.length;i++)
        {
            ans[i] = 1;
        }
        for(int i=0;i<places.length;i++)
        {
            visited = new boolean[5][5];
            for(int j=0;j<5;j++)
            {
                for(int k=0;k<5;k++)
                {
                    if(places[i][j].charAt(k) == 'P')
                    {
                        visited[j][k] = true;
                        dfs(i,0,j,k,places[i]);
                        visited[j][k] = false;
                    }
                }
            }
        }

        return ans;
    }
    void dfs(int roomNumber, int depth, int y, int x, String[] room)
    {
        if(depth > 2)
            return;
        if(depth > 0 && depth <= 2 && room[y].charAt(x) == 'P')
        {
            ans[roomNumber] = 0;
            return;
        }
        for(int i=0;i<4;i++)
        {
            int ny = y + dy[i];
            int nx = x + dx[i];
            //빈칸이거나 사람 있을때만
            if(ny >= 0 && nx >= 0 && ny < 5 && nx < 5 && room[ny].charAt(nx) != 'X')
            {
                if(visited[ny][nx])continue;
                visited[ny][nx] = true;
                dfs(roomNumber, depth+1, ny, nx, room);
                visited[ny][nx] = false;
            }
        }
    }
}

///BFS
import java.util.Queue;
import java.util.LinkedList;
class Solution
{
    int[] ans;
    boolean[][] visited;
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    public int[] solution(String[][] places)
    {
        ans = new int[places.length];
        for(int i=0;i<places.length;i++)
        {
            ans[i] = 1;
        }
        for(int i=0;i<places.length;i++)
        {
            visited = new boolean[5][5];
            for(int j=0;j<5;j++)
            {
                for(int k=0;k<5;k++)
                {
                    if(places[i][j].charAt(k) == 'P')
                    {
                        if(ans[i] == 1)
                            bfs(i,j,k,places[i]);
                    }
                }
            }
        }
        return ans;
    }
    void bfs(int roomNumber, int y, int x, String[] room)
    {
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(y, x, 0));
        visited[y][x] = true;

        while(!q.isEmpty())
        {
            int sy = q.peek().y;
            int sx = q.peek().x;
            int depth = q.peek().depth;
            q.remove();
            if(depth > 2)
                break;
            if(depth >= 1 && depth <=2 && room[sy].charAt(sx) == 'P')
            {
                ans[roomNumber] = 0;
                break;
            }
            for(int i=0;i<4;i++)
            {
                int ny = sy + dy[i];
                int nx = sx + dx[i];
                if(ny >= 0 && nx >=0 && ny < 5 && nx < 5 && room[ny].charAt(nx) != 'X')
                {
                    if(!visited[ny][nx])
                    {
                        visited[ny][nx] = true;
                        q.add(new Pos(ny,nx,depth+1));
                    }
                }
            }
        }
    }
}
class Pos{
    int y,x, depth;
    public Pos(int y, int x, int depth)
    {
        this.y = y;
        this.x = x;
        this.depth =depth;
    }
}

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력

문제 예시를 보면 numbers 의 개수 가 5개 일때 2^5개의 경우를 만들 수 있습니다.

[ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ]

 +    +     +    +     +

 -     -      -     -     -

각각의 경우에 +,- 두가지 선택 가능  따라서 2x2x2x2x2;

문제에서 numbers 최대 갯수는 20개 경우의 수는 2^20 으로 1,048,576가지 경우의 수가 있습니다.

깊이 우선 탐색을 이용해서 + 선택 -선택 두가지 갈래로 검사해 나가는 코딩을 이용해 보았습니다.

이와 비슷한 acmicpc.net에 연산자 끼워넣기가 있습니다. 한번 풀어보세요.

https://www.acmicpc.net/problem/14888

#include <iostream>
#include <vector>
using namespace std;
int answer;
void dfs(vector<int> numbers, int target, int sum, int cnt)
{
	if(cnt == numbers.size())
    {
    	if(sum == target)
        {
        	answer++;
        }
    	return;
    }
    dfs(numbers, target, sum + numbers[cnt], cnt+1);
    dfs(numbers, target, sum - numbers[cnt], cnt+1);
}

int solution(vector<int> numbers, int target)
{
	answer = 0;
    dfs(numbers, target ,0, 0);
	return answer;
}