false인 상태면 아직 해당 알파벳이 접근한 적이 없다는 뜻이고, true이면 해당 알파벳을 이미 지나왔다는 뜻이다.
시작점 (0, 0)으로부터 탐색할 수 있는 깊이 만큼 DFS를 사용해서 탐색하고, 맨끝 노드에 도달했다면
지금까지의 count를 max와 비교한다.
그리고 해당 DFS를 빠져나오면 다음 노드를 탐색하기위해 방금 그 노드의 접근 기록을 지운다
방금 노드의 alpa를 다시 false로 만들고, count도 1 뺀다.
상하좌우 순으로 순회하므로 다음과 같은 Map에서 아래와 같은 상황이 노드 끝까지 순회한 상황이다.
더이상 순회 할 수 없으므로 count를 max와 비교하고 해당 노드를 빠져나온다.
(왼)해당 순회 끝 (오)백트래킹
그러면 다음과 같이 백트래킹 과정이 일어나게 된다. 해당 노드를 방문하기 전으로 돌리는 것이다.
/* 해답코드 */
package baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class b1987 {
public static int[] dr = { -1, 1, 0,0}; //상하좌우
public static int[] dc = { 0, 0, -1,1 };
public static int R;
public static int C;
public static int max=0;
public static int count=1;
public static char[][] map;
public static boolean[] alpa = new boolean[26];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new char[R][C];
for (int r = 0; r < R; r++) {
map[r] = br.readLine().toCharArray();
}
alpa[(int)map[0][0]-65]=true;
dfs(0,0);
System.out.println(max);
}
public static void dfs(int r, int c) {
for(int d=0;d<4;d++) {
int nr = r+dr[d];
int nc = c+dc[d];
if(nr>=0&&nr<R&&nc>=0&&nc<C&&!alpa[(int)map[nr][nc]-65]) {
alpa[(int)map[nr][nc]-65]=true;
count++;
dfs(nr,nc);
alpa[(int)map[nr][nc]-65]=false;
count--;
}
if(d==3) {
if(max < count)
max = count;
}
}
}
}
유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다.
원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다.
빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다.
원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다.
가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다.
원웅이는 가스를 되도록 많이 훔치려고 한다. 따라서, 가스관과 빵집을 연결하는 파이프라인을 여러 개 설치할 것이다. 이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 즉, 각 칸을 지나는 파이프는 하나이어야 한다.
원웅이 빵집의 모습이 주어졌을 때, 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 R과 C가 주어진다. (1 ≤ R ≤ 10,000, 5 ≤ C ≤ 500)
다음 R개 줄에는 빵집 근처의 모습이 주어진다. '.'는 빈 칸이고, 'x'는 건물이다. 처음과 마지막 열은 항상 비어있다.
출력
첫째 줄에 원웅이가 놓을 수 있는 파이프라인의 최대 개수를 출력한다.
유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다.
원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다.
빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다.
원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다.
가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다.
원웅이는 가스를 되도록 많이 훔치려고 한다. 따라서, 가스관과 빵집을 연결하는 파이프라인을 여러 개 설치할 것이다. 이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 즉, 각 칸을 지나는 파이프는 하나이어야 한다.
원웅이 빵집의 모습이 주어졌을 때, 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 R과 C가 주어진다. (1 ≤ R ≤ 10,000, 5 ≤ C ≤ 500)
다음 R개 줄에는 빵집 근처의 모습이 주어진다. '.'는 빈 칸이고, 'x'는 건물이다. 처음과 마지막 열은 항상 비어있다.
출력
첫째 줄에 원웅이가 놓을 수 있는 파이프라인의 최대 개수를 출력한다.
/* 풀이방법 */
DFS탐색을 사용해서 풀었다.
파이프 시작부분을 돌면서 DFS를 구현한 재귀함수를 돈다. 오른쪽 위, 오른쪽, 오른쪽 아래 순으로 탐색하게 된다.
만약 아직 해당 파이프가 출발지에 도착하지 못했다면 방문했다는 표시로 "X"를 표시한다.
이미 도착한 이후는 순회할 필요가 없으므로, successed라는 전역 boolean 변수를 생성하여 도착했을때 true로 바꿔준다.
그러면 다음 파이프 출발지를 시작하기 전까지는 남은 재귀함수를 순회한다거나 방문을 표시하지 않는다.
1번째 줄 파이프를 순회한 모습
2번째 줄 파이프를 순회한 모습
3번째 줄 파이프를 순회한 모습
4번째 줄 파이프를 순회한 모습
마지막 줄은 방문할 수 있는 곳이 없다!
그래서 완주에 성공한 개수인 2가 출력되게 된다.
/* 해답코드 */
package baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
//빵집
public class b3109 {
public static int[] dr = { -1, 0, 1 };
public static int R;
public static int C;
public static int result = 0;
public static boolean successed;
public static String[][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new String[R][C];
for (int r = 0; r < R; r++) {
String[] temp = br.readLine().split("");
map[r] = temp;
}
for (int i = 0; i < R; i++) {
successed = false;
dfs(i, 0);
}
System.out.println(result);
}
public static void dfs(int r, int c) {
if(successed) {
return;
}
else if(c==C-1) {
successed=true;
result++;
return;
}
for(int d=0; d<3; d++) {
int nr = r+dr[d];
int nc = c+1;
if(nr>=0&&nr<R&&!map[nr][nc].equals("x")) {
if(!successed)
map[nr][nc]="x";
dfs(nr,nc);
}
}
}
}
흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.
주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다
위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.
출력
영상을 압축한 결과를 출력한다.
/* 풀이방법 */
첫번째 값만 저장해놓고 해당 사이즈만큼 전체를 순회하다가 첫번째 값과 다른 값이 발견되면
사이즈를 1/2로 줄이고, 현재지점을 x,y라 할때
1사분면 - (x,y)부터 줄여진 사이즈만큼 순회
2사분면 - (x,y+사이즈)부터 줄여진 사이즈 만큼 순회
3사분면 - (x+사이즈,y)부터 줄여진 사이즈 만큼 순회
4사분면 - (x+사이즈,y+사이즈)부터 줄여진 사이즈 만큼 순회
다음과 같이 재귀 호출 한다.
해당 사이즈만큼의 크기가 모두 같은 값이거나, 사이즈가 1이라면 해당 숫자를 프린트 한다.
/* 해답코드 */
package baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
//쿼드트리
public class b1992 {
public static String[][] map;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
map = new String[N][N];
for(int i=0;i<N;i++) {
map[i]=br.readLine().split("");
}
quadTree(N,0,0);
}
public static void quadTree(int size,int x,int y) {
String start = map[x][y];
if(size==1) {
System.out.print(start);
return;
}
for(int i=x;i<x+size;i++) {
for(int j=y;j<y+size;j++) {
if(!start.equals(map[i][j])) {
size/=2;
System.out.print("(");
quadTree(size,x,y);
quadTree(size,x,y+size);
quadTree(size,x+size,y);
quadTree(size,x+size,y+size);
System.out.print(")");
return;
}
}
}
System.out.print(start);
}
}
가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오른쪽 위 45도 방향으로 일정한 속력으로 움직이기 시작한다. 처음에 (p,q)에서 출발한 개미는 1시간 후에는 (p+1,q+1)로 옮겨간다. 단, 이 속력으로 움직이다가 경계면에 부딪치면 같은 속력으로 반사되어 움직인다.
위 그림은 6×4 격자에서 처음에 (4,1)에서 출발한 개미가 움직인 길을 보여주고 있다. 처음에 (4,1)에 있는 개미는 2시간 후에 (6,3)에 있으며 8시간 후에 (0,1)에 있다. 만일 그 개미가 처음에 (5,3)에 있었다면 매 시간마다 (6,4), (5,3), (4,2), (3,1)로 움직인다.
여러분은 크기 w×h인 격자 공간에서 처음에 (p,q)에서 출발하는 개미의 t시간 후의 위치 (x,y)를 계산하여 출력해야 한다. 개미는 절대 지치지 않고 같은 속력으로 이동한다고 가정한다.
문제에서 w와 h는 자연수이며 범위는 2 ≤ w,h ≤ 40,000이다. 그리고 개미의 초기 위치 p와 q도 자연수이며 범위는 각각 0 < p < w과 0 < q < h이다. 그리고 계산할 시간 t의 범위는 1 ≤ t ≤ 200,000,000이다.
입력
첫줄에는 w와 h가 공백을 사이에 두고 주어진다. 그 다음 줄에는 초기 위치의 좌표값 p와 q가 공백을 사이에 두고 주어진다. 3번째 줄에는 개미가 움직일 시간 t가 주어진다.
출력
출력은 t 시간 후에 개미의 위치 좌표 (x,y)의 값 x와 y를 공백을 사이에 두고 출력한다.
/* 풀이방법 */
대각선으로 움직이는 것은 결국 가로한칸, 세로한칸을 동시에 움직이는 것과 같다!
그리고 높이나 너비로 나누었을때 해당 숫자가 짝수이면 0부터 시작, 홀수이면 벽에서부터 시작한다.
이점을 고려해서 반복문없이 푸는데 성공했으나,
StringBuilder를 사용하지 않아 계속 시간초과가 나서 매우 괴로웠다 ㅠ
(다음 스터디에서는 StringBuilder에 대해 더 공부해봐야겠다.)
/* 해답코드 */
package baekjoon;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
//개미
public class b10158 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int W = Integer.parseInt(st.nextToken());
int H = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int T = Integer.parseInt(br.readLine());
//짝수면 0에서 출발, 홀수면 벽에서 출발
boolean moveX = (x+T)/W%2==0;
boolean moveY = (y+T)/H%2==0;
x=(x+T)%W;
if(!moveX) {
x=W-x;
}
y=(y+T)%H;
if(!moveY) {
y=H-y;
}
StringBuilder sb = new StringBuilder();
sb.append(x);sb.append(" ");sb.append(y);
bw.write(sb.toString());
bw.flush();
bw.close();
}
}
