WantAirpod

www.acmicpc.net/problem/2309

문제풀이

• dfs를 통해 9명 중 7명을 뽑는 Combination(조합)을 해주는 문제
• 조합 코드 : 다시 for문으로 갈때 i=x부터 시작하는것이 중요! visit 중요 !
• sum==100 이면 바로 탈출 dfs 진입 처음 if문에 flag 이용 !

	for(int i = x ; i<9 ; i++)
		{
			if(flag == true)
				break;
			if(vi[i]==false)
			{
				vi[i]=true; 
				//sum = sum + Nan[i];
				dfs(x+1,num+1,sum+Nan[i]);
				
				//sum = sum -Nan[i];
				vi[i]=false;	
			}			
		}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool visit[9] = { false, };
int arrNuan[9] = { 0, };
bool flag = false;
vector<int> v;
void input()
{

	for (int i = 0; i < 9; i++)
	{
		int temp;
		cin >> temp;
		arrNuan[i] = temp;
	}
}
void dfs(int p,int cnt, int sum)
{	
	if (cnt == 7)
	{
		if (sum == 100)
		{
			flag = true;
			sort(v.begin(), v.end());
			for (auto i : v)
			{
				
				cout << i << endl;
			}
		}
		return;
	}

	for (int w = p; w < 9; w++)
	{
		if (!visit[w])
		{
			visit[w] = true;
			v.push_back(arrNuan[w]);
			dfs(w, cnt+1, sum + arrNuan[w]);
			if (flag) break;
			 

			v.pop_back();
			visit[w] = false;
		}

	}
}

int main()
{
	visit[9] = { false, };
	arrNuan[9] = { 0, };
	flag = false;
	for (int i = 0; i < v.size(); i++)
		v.pop_back();
	input();
	dfs(0,0,0);

	return 0;
}

Java

package Z_ShinHanCard_Prepare;
import java.util.*;
public class D2백준2309_일곱난쟁이_DFS {

	//9C7 뽑는 경우의 수 !!
	static int[] Nan =  new int[9];;
	static boolean[] vi = new boolean[9];;
	static ArrayList<Integer> arr =new ArrayList<Integer>();
	static boolean flag; 
	static void dfs(int x, int num,int sum)
	{
		
		if(num==7)
		{
			if(sum==100)
			{
				//arr = new ArrayList<Integer>();
				for(int i =0  ; i < 9 ; i++ )
				{
					if (vi[i]==true)
					{
						arr.add(i);
					 
					}
					flag=true;
				 
				}
			}
			return;
		}
		
		for(int i = x ; i<9 ; i++)
		{
			if(flag == true)
				break;
			if(vi[i]==false)
			{
				vi[i]=true; 
				//sum = sum + Nan[i];
				dfs(x+1,num+1,sum+Nan[i]);
				
				//sum = sum -Nan[i];
				vi[i]=false;	
			}			
		}
		
	}
	public static void main(String[] args) 
	{
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		for(int i =0 ; i < 9 ; i ++)
		{
			int temp = sc.nextInt();
			Nan[i] = temp;
		}
		
		dfs(0,0,0);
		
		ArrayList<Integer> answer = new ArrayList<Integer>();
		for(int x : arr)
		{
			answer.add(Nan[x]); 
		}
		Collections.sort(answer);
		
		for(int x : answer)
		{
			System.out.println(x);
		}
		
		
		
	}

}

www.acmicpc.net/problem/2178

문제풀이

• 입력 받는 부분 tip (String 으로 받아도 -'0' 해주면 int로 돌아온다.

		map = new int[R][C];
		visit= new boolean[R][C];
		for(int i =0 ; i <R ; i++)
		{
			String input1 = br.readLine();
			for(int j = 0 ; j < C ; j++ )
			{
				map[i][j] = input1.charAt(j) - '0'; 
			}
		}

• BFS를 돌면서 이동 가능한 칸은 자기자신의 숫자+1 결국 (최단거리)

C++ 

#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;


int ar[101][101];
int vi[101][101];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int n, m, ans = 1000000;

queue<pair<int, int>> q;




void input()
{
	cin >> n >> m;
	// nxm 짜리 
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%1d", &ar[i][j]); //꿀팁
		}
	}
}

void bfs() {
	q.push({ 0, 0 });
	vi[0][0] = 1;
	ar[0][0] = 0;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (x == n - 1 && y == m - 1)
		{
			ans = vi[x][y];
			break;
		}


		for (int w = 0; w < 4; w++)
		{
			int nx = x + dx[w];
			int ny = y + dy[w];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

			if (vi[nx][ny] == 0 && ar[nx][ny] == 1)
			{
				
				vi[nx][ny] = vi[x][y] + 1;
				q.push({ nx, ny });
			}

		}

	}

}

void dfs(int x, int y, int su) {
	if (x == n - 1 && y == m - 1) {
		ans = min(su, ans);
		return;
	}

	for (int w = 0; w < 4; w++)
	{
		int nx = x + dx[w];
		int ny = y + dy[w];
		if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
		if (vi[nx][ny] == 0 && ar[nx][ny] == 1) 
		{
			
			vi[nx][ny] = vi[x][y] + 1;
			dfs(nx, ny, vi[nx][ny]);
			vi[nx][ny] = 0;
		}
	}
}

int main()
{
	input();
	bfs();
	cout << ans  << endl;
	return 0;
}

Java

package Z_ShinHanCard_Prepare;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Box
{
	int x;
	int y;
	int z;
	public Box(int x, int y)
	{
		this.x = x;
		this.y = y;
		this.z = z;
	}
}
public class D2백준2178_미로탐색_DFSBFS 
{
	static int R,C,Z;
	static int[][] map;
	static boolean[][] visit;
	static int[] dx = { -1,1,0,0};
	static int[] dy = { 0,0,-1,1};
	
	static void bfs(int x, int y)
	{
		Queue<Box> q = new LinkedList<Box>(); 
		q.add(new Box(x,y));
		while(!q.isEmpty())
		{
			Box box = q.poll();
			for(int w=  0 ; w< 4 ; w++)
			{
				int nx = box.x + dx[w];
				int ny = box.y +dy[w];
				if(nx<0 || nx>=R || ny <0 || ny >=C)
					continue;
				if(visit[nx][ny])
					continue;
				if(map[nx][ny] == 0)
					continue;
				q.add(new Box(nx,ny));
				visit[nx][ny] = true;
				box.z = map[nx][ny]+1;
				map[nx][ny] = map[box.x][box.y] + 1;
						
			}
			
			
		}
	}
	public static void main(String[] args) throws IOException 
	{
		
		// TODO Auto-generated method stub
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		StringTokenizer st= new StringTokenizer(input);
		R= Integer.parseInt(st.nextToken()); //4
		C= Integer.parseInt(st.nextToken()); //6
		
		map = new int[R][C];
		visit= new boolean[R][C];
		for(int i =0 ; i <R ; i++)
		{
			String input1 = br.readLine();
			for(int j = 0 ; j < C ; j++ )
			{
				map[i][j] = input1.charAt(j) - '0'; 
			}
		}
		
		visit[0][0] =true;
		bfs(0,0);
		System.out.println(map[R-1][C-1]);
		

	}

}

www.acmicpc.net/problem/1260

문제풀이

• 노드연결이 중요함.
• dfs/bfs 이해
• check 배열 중요 !

DFS : 1->2->4->3

BFS : 1->2->3->4 //1에서 이미 다 Queue에 들어가면서 방문.

C++

Java

package Z_ShinHanCard_Prepare;

import java.util.*;

public class D2백준1260_DFSBFS {
	static int N, M, K;
	static boolean[] check;
	static ArrayList<Integer>[] arr;

	public static void dfs(int s) {
		if (check[s])
			return;
		check[s] = true;
		System.out.print(s + " ");
		for (int y : arr[s]) {
			if (check[y] == false) {
				dfs(y);
			}
		}
	}

	public static void bfs(int s) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(s);
		
		check[s] = true;
		while (!q.isEmpty()) {
			int x = q.poll();			
			System.out.print(x+" ");
			for (int w = 0; w < arr[x].size(); w++) 
			{
				int nx = arr[x].get(w);
				if (check[nx])
					continue; 
				q.add(nx);
				check[nx] = true; 
			}

		}

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		// TODO Auto-generated method stub
		N = sc.nextInt();
		M = sc.nextInt();
		K = sc.nextInt();
		arr = new ArrayList[N + 1];

		for (int i = 0; i <= N; i++) {
			arr[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < M; i++) {
			int u, v;
			u = sc.nextInt();
			v = sc.nextInt();
			arr[u].add(v);
			arr[v].add(u);
		}
		for (int i = 0; i < arr.length; i++) {
			Collections.sort(arr[i]);
		}
		check = new boolean[N + 1];
		dfs(K);
		check = new boolean[N + 1];
		System.out.println();
		bfs(K);

	}

}

www.acmicpc.net/problem/12871

해결방법

• ab <-> abab 일 경우
• 포인터를 있다고 가정하여 문자열이 끝나면 다시 0으로 옮겨 주는 방법

코드

C++

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string s, t;
int che = 0;

void solve() {
	 
	if (s.size() > t.size()) swap(s, t); // swap 개꿀... 
	int a = 0; int b = 0;
	bool flag = false;
	int ct = 0;
	while (ct <= 500) {
		if (s[a] != t[b]) {
			che = 0;
			flag = true;
			break;
		}
		a++;
		b++;
		if (a == s.size()) a = 0;
		if (b == t.size()) b = 0;
		ct++;
	}

	if (!flag) che = 1;
}

int main() {
	cin >> s >> t;
	solve();
	cout << che << endl;
	return 0;
}

Java

import java.io.*;

public class Main {

	 static int che =0;
	public static void main(String[] args) throws Exception  {
		// TODO Auto-generated method stub

		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();//ab
		String t = br.readLine();//abab
 
		if(s.length() > t.length())
		{
			String tmp;
			tmp = s;
			s = t;
			t = tmp;
		}
		
		int a=0;
		int b=0;
		boolean flag = false;
		int ct = 0;
		while(ct<=500)
		{
			if(s.charAt(a) != t.charAt(b))
			{
				che = 0;
				flag = true;
				break;
			}
			a++;
			b++;
			if(a==s.length())
				a=0;
			if(b==t.length())
				b=0;
			ct++;
		}
		
		if(!flag) che=1; 
		
		System.out.println(che);	
	}

}

www.acmicpc.net/problem/2667

풀이방법

• BFS로 순회하면서 visit처리해준다.
• 단지가 끝나면 새로운 단지를 찾는다. 찾으면 총 단지수를 ++ 해준다
• 새로운 단지 BFS하며 q에서 pop할때 마다 각 단지의 수 해주어 각 단지의 갯수를 구한다.
• Java에서 Vector 대신 List를 써주며 sort 법이 조금 다르다.

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int ar[26][26];
int vi[26][26];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int n;
vector<int> v;
vector<int> ans;
int ct = 0; int ct2 = 0;

void input() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) scanf("%1d", &ar[i][j]);
	}
}

void bfs(int i, int j) {
	ct = 0;
	ct2++;
	queue<pair<int, int>> q;
	q.push({ i, j });
	vi[i][j] = 1;
	while (!q.empty()) 
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		ct++;

		for (int w = 0; w < 4; w++) {
			int nx = x + dx[w];
			int ny = y + dy[w];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n)
				continue;
			if (ar[nx][ny] != 0 && vi[nx][ny] == 0) 
			{
				vi[nx][ny] = 1;
				q.push({ nx, ny });
			}
		}
	}

	v.push_back(ct);
}

void solve() {
	for (int i = 0; i < n; i++) 
	{
		for (int j = 0; j < n; j++) 
		{
			if (ar[i][j] != 0 && vi[i][j] == 0) 
				bfs(i, j);
		}
	}
	ans.push_back(ct2);
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) ans.push_back(v[i]);
}

int main() {
	input();
	solve();
	for (int i = 0; i < ans.size(); i++) cout << ans[i] << endl;
	return 0;
}

Java

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*; 

class Node
{
	int x;
	int y;
	ArrayList<String> list;
	Node(int x, int y)
	{
		this.x = x;
		this.y = y;
		this.list =new ArrayList<String>();
	}
}

public class 백준2667_단지번호붙히기_DFSBFS1 
{
	ArrayList<ArrayList<String>> list4 = new ArrayList<ArrayList<String>>();
	static int house[][];
	static boolean[][] visited;
	static int N;
	static int dir_x[]= {-1,1,0,0};
	static int dir_y[]= {0,0,-1,1};
	
	static ArrayList<Integer> listall= new ArrayList<Integer>();
	static ArrayList<Integer> list= new ArrayList<Integer>();
	//static Stack<Node> stck= new Stack<Node> ();
	static int count=0;
	static int ct =0;
	static int ct2 =0;
	
	public static void bfs(int i, int j )
	{
		ct =0;
		ct2++;
		Queue <Node> q = new LinkedList<Node> ();
		q.add(new Node(i,j));
		while(!q.isEmpty())
		{
			Node p = q.poll(); 
			int x = p.x;
			int y = p.y;
			visited[x][y] =true;
			ct++;
			for(int w= 0 ; w <4 ; w++)
			{
				int nx = x + dir_x[w];
				int ny = y + dir_y[w];
				
				if (nx <0 || nx >=N || ny < 0 || ny >=N)
					continue;
				if(visited[nx][ny])
					continue;
				if(house[nx][ny] !=0)
				{
					q.add(new Node(nx,ny));
					visited[nx][ny] =true;	
				}
				
			}
					
		}
		
		list.add(ct);
	}
	
	
	public static void solve()
	{
		for (int i = 0; i < N; i++) 
		{
			for (int j = 0; j < N; j++) 
			{
				if (house[i][j] != 0 && visited[i][j] == false) 
					bfs(i, j);
			}
		}
		listall.add(ct2);
		Collections.sort(list);
		for(int i = 0 ; i<list.size();i++)
		{
			listall.add(list.get(i));
		}
	}
	
	public static void main(String[] args) throws IOException 
	{
		BufferedReader br= new BufferedReader (new InputStreamReader(System.in));
		String input= br.readLine();
		N = Integer.parseInt(input);
		house = new int [N][N];
		visited = new boolean [N][N];
		//Arrays.fill(visited, false);
		for(int i = 0 ; i < N; i++)
		{
			input = br.readLine();
			for(int j =0 ; j < N ; j++)
			{
				int tempNum = input.charAt(j);
				house[i][j] = input.charAt(j) -'0'; 
			}
		}
		solve();
		
		//System.out.println(list.size());
		for (int i=0; i<listall.size(); i++)
		{
			System.out.println(listall.get(i));
		}
		// TODO Auto-generated method stub

	}

}

www.acmicpc.net/problem/1987

문제해설

• DFS 로 문제풀이 
• DFS 로 순회하면서 다른 문자가 나타나면 Count++
• 4 방향 다 돌고 같은 문자 만날시 나와주면서 Count--; 방문 취소 처리 재귀

SOL

C++

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>

using namespace std;

bool visit[26];
int n, m;
char arr[25][25];
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };
int answer = 0;
 
void dfs(int cnt, int ii, int jj)
{
	answer = max(answer, cnt);

	 
	for (int w = 0; w < 4; w++)
	{
		int nx = ii + dx[w];
		int ny = jj + dy[w];

		if (nx < 0 || ny < 0 || nx>=n || ny >=m )
		{
			continue;
		}
		if (visit[arr[ii][jj] - 'A'] == false)
		{  
			visit[arr[ii][jj] - 'A'] = true;
			dfs(cnt + 1, nx, ny);
			visit[arr[ii][jj] - 'A'] = false;

		}
	}

	 
}
void input()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		string temp;
		cin >> temp;

		for (int j = 0; j < m; j++)
		{
			arr[i][j] = temp[j];
		}
	}
}
int main()
{
 
	input();
	dfs(0, 0, 0);
	cout << answer << endl;
	return 0;
}

Java

package Z_ShinHanCard_Prepare;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class 백준1987_알파벳_DFSBFS 
{
	static int R;
	static int C;
	static int dir_x[]= {-1,1,0,0};
	static int dir_y[]= {0,0,-1,1};
	static char map[][];
	static int visited[][];
	static String str= "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	static int alpha[]= new int[str.length()];
	static int count=1;
	static int answer=1;
	public static void search (int x, int y) {
		char curr=map[x][y];
		
		
		alpha[str.indexOf(curr)]=1;
		for (int i=0; i<4; i++) {
			int next_x=x+dir_x[i];
			int next_y= y+dir_y[i];
			
			if (next_x<0 || next_x>=R ||next_y<0 || next_y>=C) continue;
			int temp= map[next_x][next_y];
			int temp2 = str.indexOf(temp);
			if (alpha[str.indexOf(temp)]==1) continue;
			count++;
			answer= Math.max(answer, count);
			search(next_x, next_y);
			
		}
		count--;
		alpha[str.indexOf(curr)]=0;
	}
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		String input= br.readLine();
		StringTokenizer st= new StringTokenizer(input);
		R= Integer.parseInt(st.nextToken());
		C= Integer.parseInt(st.nextToken());
		map= new char [R][C];
		visited= new int [R][C];
		Arrays.fill(alpha, 0);
		for (int arr[]: visited) {
			Arrays.fill(arr, 0);
		}
		
		for (int i=0; i<R; i++) {
			input= br.readLine();
			for (int j=0; j<C; j++) {
				map[i][j]= input.charAt(j);
			}
		}
		search(0,0);
		System.out.println(answer);
		
	}

}

www.acmicpc.net/problem/1697

문제해석

• 수빈이가 동생을 잡으려고 하는데 2*X, X+1, X-1로 이동 가능함
• 최소의 이동으로 동생의 위치에 도달하는 방법 찾기 (=최적의 길)-> BFS
• 오직 BFS로만 풀리는 문제

SOL

• BFS로 구현

#include <iostream>
#include <queue>

using namespace std;

int n, m, ans;
queue<pair<int, int>> q;
bool vi[1000001];

void solve() {
	q.push({ n, 0 });
	vi[n] = 1;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (x == m) {
			ans = y;
			break;
		}

		for (int w = 0; w < 3; w++) {
			if (w == 0 && vi[x - 1] == 0 && x - 1 >= 0) {
				q.push({ x - 1, y + 1 });
				vi[x - 1] = 1;
			}
			else if (w == 1 && vi[x + 1] == 0 && x + 1 < 100001) {
				q.push({ x + 1, y + 1 });
				vi[x + 1] = 1;
			}
			else if (w == 2 && vi[x * 2] == 0 && x * 2 < 100001) {
				q.push({ x * 2, y + 1 });
				vi[x * 2] = 1;
			}
		}
	}
}

int main() {
	cin >> n >> m;
	solve();
	cout << ans << endl;
	return 0;
}

Java

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

class Location
{
	int x;
	int y;
	Location(int x, int y)
	{
		this.x = x;
		this.y = y;
	}
	}

public class Main
{
	static boolean[] vi = new boolean[100001];
		
	public static void bfs(int a, int b)
	{
		Arrays.fill(vi, false);
		Queue<Location> q = new LinkedList<Location>();
		
		q.add(new Location(a,0));
		vi[a] = true;
		
		while(!q.isEmpty())
		{
			Location temp = q.poll();
			
			if(temp.x == b)
			{
				System.out.print(temp.y);
				break;
			}
			
			int x = temp.x;
			int y = temp.y;
			
			x = temp.x-1;
			y = temp.y+1;
			
			if(x>=0 && vi[x] == false)
			{
				vi[x] = true;
				q.add(new Location(x,y));
			}
			
			
			x = temp.x+1;
			y = temp.y+1;
			
			if(x<=100000 && vi[x] == false)
			{
				vi[x] = true;
				q.add(new Location(x,y));
			}
			
			x = temp.x *2;
			y = temp.y+1;
			
			if(x<=100000 && vi[x] == false)
			{
				vi[x] = true;
				q.add(new Location(x,y));
			}
			
		}
		
	}
	
    public static void main(String[] args) throws IOException
    {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	String str = br.readLine();
    	StringTokenizer st = new StringTokenizer(str);
    	int a = Integer.parseInt(st.nextToken());
    	int b  = Integer.parseInt(st.nextToken());
    	
    	bfs(a,b); 
    	
        
        
    }
}

programmers.co.kr/learn/courses/30/lessons/1845

문제해설

• nums에 폰켓몬 번호가 주어짐 (같은 번호는 같은 폰켓몬)
• 고를 수 있는 폰켓몬은 nums의 갯수 / 2 
• 최대한 result 가지의 폰켓몬을 고르는 방법 

sol

• Set을 이용하여 구현 
• 중복제거 한 Set의 갯수와 nums/2 의 갯수 중 더 큰 값이 답.

C++ 

#include <vector>
#include <set>
#include <iostream>
using namespace std;

int solution(vector<int> nums)
{
    int answer = 0;
    set<int> s;
    for(int i = 0 ; i < nums.size() ; i++)
    {
        s.insert(nums[i]);
    }
  
    int com = nums.size()/2;
    if(s.size() > com )
    {
        answer =com;
    }
    else
    {
        answer = s.size();
    }
    
    return answer;
}

Java 

• Java는 C++의 set이 아닌 HashSet을 씀

import java.util.*;

public class 프로그래머스Lv2_폰켓몬_HashSet {

 
    static int solution(int[] nums) 
    {
        int answer = 0;
        HashSet<Integer> s = new HashSet<Integer>();
        //set<integer> s;
        for(int i = 0 ; i<nums.length ;i++)
        {
        	s.add(nums[i]);
        }
        int tempNum = nums.length /2;
        if(s.size() > tempNum )
        	answer = tempNum;
        else
        	answer = s.size();
        
        return answer;
   
    }
	public static void main(String[] args) {
		// TODO Auto-generated method stub
	 
		int nums1 []= {3,1,2,3}; 
		solution(nums1); 
	}
	
}