출저 : https://www.acmicpc.net/problem/6987 "가능한 모든 경기 결과를 탐색해 주어진 결과를 만족하는 경우가 있는지 찾자" 처음 이 문제를 너무 단순하게 생각했다. 각 조에서 이루어진 경기 결과 중 승과 패가 같고, 무승부인 경우가 짝수개로 나오는지만 확인하면 되는 줄 알고, 그렇게 해서 애를 먹었다.. 제대로된 접근 방법은 각 조의 6개의 국가가 돌아가면서 모두 한번씩 경기를 치룬다고 했으니 가능한 경기는 아래와 같이 총 15개 이다. A : {B,C,D,E,F}B : {C,D,E,F}C : {D,E,F}D : {E,F}E : {F} 경기의 순서는 상관 없다. 이 15개의 경기에서 매 경기 가능한 결과 (A 가 이기고 B가 지고 , B가 지고 B가 이기고, A 와 B가 무..
출저 : https://www.acmicpc.net/problem/7576 "단순 BFS" 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer; public class ..
출저 : https://www.acmicpc.net/problem/1697 "단순 BFS" 수빈이가 이동할 수 있는 방법을 길이 3인 배열로 만들어 처리했음. 12345678910111213141516171819202122232425262728293031323334353637383940414243import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer; public class Main { static int N,K; static int INF = 1000..
출저 : https://www.acmicpc.net/problem/4179 "불먼저 사람먼저 두 번의 BFS, 트리의 level을 카운터로" 지훈이가 불을 피해 가장자리 까지 가서 몇번 만에 탈출할 수 있는지 최단거리를 구하는 문제이다. 이 문제에서 중요한 것은 불과 지훈이용 큐 두개를 가지고 BFS를 두번 돌리는 것이다. 불을 먼저 보내고 그 후에 지훈이가 갈 수 있는 경로를 탐색해야함을 주의한다. 순서가 중요하다. 이동 횟수는 count 변수를 두어 BFS 전체에서 구한다. 이 값이 트리의 level 이라고 할 수 있다. 이 때 fs,ms 와 같은 size 변수를 두어 BFS 탐색을 함에 주의한다. 123456789101112131415161718192021222324252627282930313233..
출저 : https://www.acmicpc.net/problem/2667 "단순 BFS" BFS를 돌려서 상하좌우로 인접해 있는 집들을 탐색한다. 탐색하는 과정에서 각 단지를 넘버링 할 수 있는 변수를 하나 두고, BFS 탐색이 끝날 때마다 변수를 증가 시켜 넘버링을 이루게 한다. 이와 비슷한 형식으로 매 BFS 탐색마다 단지의 개수를 세는 count 변수를 하나 두어 단지의 개수를 세고, 아래 풀이에서는 이 카운트 값을 Array List에 넣어두고, 나중에 sort 하였다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768..
출저 : https://www.acmicpc.net/problem/6603 "재귀 함수를 활용한 DFS 완전탐색" 해당 문제의 분류는 BFS로 되어있었는데, 흠... DFS가 훨씬 풀기 쉬운 것 같다. 먼저 주어진 숫자 k 중에서 6개를 뽑는 경우의 수를 사전순으로 출력하는 것이다. 따라서 완전 탐색을 해주면 되겠다. 여기서 한가지 팁은 k 가 8일 때 가장 앞에 올 수 있는 배열의 index는 무엇일까... 당연히 0,1,2 가 되겠다. 따라서 dfs 시작 for문에서 [0,k-8) 까지만 검색 하면되겠다... 백트래킹 과정에서 어랏... 앞에 지나온 집합 원소들이 찍히질 않아서 당황했지만, for문을 돌아 방문한 배열들을 다시 탐색해 그냥 찍어주었따. 123456789101112131415161718..
출저 : https://www.acmicpc.net/problem/11559 "BFS를 활용한 구현" 먼저 뿌요뿌요의 실행 순서를 보자. 1. 중력에 의해 모든 뿌요들이 밑으로 떨어진다. 2. 상하좌우로 4개 이상 인접한 같은 색깔의 뿌요들은 모두 동시에 터진다. 간단히 두개의 과정으로 나타낼 수 있다. 이를 구현해주면 끝. 먼저 뿌요들을 밑으로 내리는 코드를 보면 아래와 같다. 12345678910111213141516for (int i = 11; i >=0 ; i--) { for (int j = 0; j
출저 : https://www.acmicpc.net/problem/2146 "BFS 두번" 각각의 섬들에 2부터 시작하는 넘버링을 한다. 이 과정은 BFS를 사용한다. 넘버링 까지는 쉽게 할 수 있다. 체크한 땅들에 대해서는 visited 배열을 통해 중복을 제거해준다. 그렇게 2 ~ .. 넘버링을 하였으면 이제 isEdge 함수를 활용해 각 섬의 모든 가장자리에서 시작해서 탐색을 시작하여 다른 섬을 만날 때 까지 탐색을 한다. 다른 섬을 구분하는 구문은 아래와 같다. if(map[cur.x][cur.y] != idx && map[cur.x][cur.y] > 0) {q.clear();break loop;} 1234567891011121314151617181920212223242526272829303132..
출저 : https://www.acmicpc.net/problem/1600 "나이트 처럼 갈 수 있는 이동이 중요한 BFS" 처음에 해당 문제를 그냥 최단거리를 구하는것 처럼 int[][] visited 배열을 두어 최대값으로 세팅하고, 특정 위치에서 최소가 되는 경우만 탐색을 진행하도록 했다. 여기서 간과한 것이... 특정위치에 나이트를 한번 쓰고 온 것과 안 쓰고 온 것은 다르다는 것이다. 아래와 같은 경우를 보자. 먼저 나이트 이동으로 (0,0) 에서 (1,2) 로 이동해서 visited[1][2] = 1 (이동횟수) 이 된다고 하면, 원숭이의 걸음으로 3번 이동해서 온 경우는 더이상 탐색을 하지 못하게 된다. (이미 최소 크기로 해당경로를 지나갔기 때문에..) 정상적이라면 최단 거리는 4가 되지만..
출저 : https://www.acmicpc.net/problem/2606 "BFS" 해당 문제는 정말 단순한 BFS 문제이다. 1번 노드를 시작으로 연결된 모든 노드들의 개수를 세면 된다. 먼저 주어진 정보를 토대로 인접행렬 adj를 만든다. 그후 BFS 에 따라 queue 에 연결된 노드들을 하나씩 넣어주고 탐색한다. 간단하다. 1번 노드는 세지 카운트 하지 않음을 주의한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamRead..
- Total
- Today
- Yesterday