7월 4째주 스터디 준비
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
문제 요약 : 다른 그래프 문제와 같이 1이 연속으로 인접해있는 정점들의 개수를 구하는 문제이다.
단지번호 붙이기 문제와 다른점은 모든 그래프가 주어지느냐 아니면 1이 입력된 정점만 주어지느냐의 차이인것 같다.
변수
T : 테스트 케이스의 개수
M : 배추밭(그래프)의 가로길이
N : 배추밭(그래프)의 세로길이
K : 배추의 위치(1이 입력된 정점)의 개수
x : 배추(정점)의 x 좌표값
y : 배추(정점)의 y 좌표값
graph[][] : 배추밭
cnt : 배추흰지렁이 한마리가 처리한 밭 수
answer : 필요한 배추흰지렁이 마리수
dfs(y,x) : y,x에 연결된 정점을 구하는 메서드
풀이 방식 - (깊이 우선탐색 방식)
그래프를 순회하면서 그래프의 값이 1이면 dfs 함수를 실행하고, 1이 아니면 리턴한다.
(그래프를 이미 체크했다는 것을 확인 시켜주기 위해 dfs함수를 실행할 때 그래프의 값을 1늘려준다.)
해당 dfs를 종료할때 answer에 cnt를 추가해 준다.
| 2 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
cnt = 3
answer = {3}
| 2 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
cnt = 2
answer = {3,2}
.
.
.
| 2 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 2 | 2 | 0 | 0 | 0 | 2 | 2 | 2 |
| 0 | 0 | 0 | 0 | 2 | 0 | 0 | 2 | 2 | 2 |
cnt = 6
answer = {3,2,2,6,1}
종료
그래프순회를 모두 마친 후 answer의 size를 통해 배추흰지렁이 마리 수를 출력해준다.
다음 테스트케이스가 있으면 반복.
**
그래프를 순회할 때 그래프의 주변값이 1인지 아닌지 확인을 해주는 방법으로
dfs() 메서드에
y, x+1
y, x-1
y+1, x
y-1, x
을 넣어 보면서 확인하는데
만약 그래프의 위치가 끝쪽일 경우 예를들어 x=1, y=0인경우 y축으로 -1가게 되면
dfs (-1, 1)가 실행되고 graph[-1][1] 이 입력이 되는데 graph[-1][1]값이 없으므로 에러가 발생하는 문제가 생긴다.
이를 해결해주기 위해
테두리에 빈값을 임의로 만들어 주었다.
예를들어
1 1 1
1 0 1
1 1 1
이라는 그래프가 있다고 하면
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
이렇게 0으로 둘러싸 주고 입력을 x,y 인덱스를 0부터가 아닌 1부터 받으면 해결된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class 유기농배추_1012 {
static int T, N, M, K, cnt;
static int[][] graph;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//테스트케이스개수
T = Integer.parseInt(br.readLine());
for (int c = 0; c < T; c++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
//세로길이
N = Integer.parseInt(st.nextToken());
//가로길이
M = Integer.parseInt(st.nextToken());
// 배추위치 개수
K = Integer.parseInt(st.nextToken());
graph = new int[N + 2][M + 2];
for (int i = 0; i < K; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
int y = Integer.parseInt(st2.nextToken());
int x = Integer.parseInt(st2.nextToken());
graph[y + 1][x + 1] = 1;
}
//여기까지 입력 받아오기
ArrayList<Integer> answer = new ArrayList<>();
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
//그래프에 값이 1이면 dfs실행
//이미 체크된 집들은 dfs내에서 1을 증가시켜줬기때문에 체크되지 않음
if (graph[i][j] == 1) {
cnt = 0;
dfs(i, j);
answer.add(cnt);
}
}
}
System.out.println(answer.size());
}
}
static void dfs(int y, int x) {
//그래프 값이 1이 아니면 리턴
if (graph[y][x] != 1) {
return;
} else if (graph[y][x] == 1) {
//그래프값이 1이면 해당 값을 +1해줘서 체크했다는것을 표시하고 cnt+1
graph[y][x]++;
cnt++;
//상하좌우로 1칸씩 이동하면서 체크
dfs(y + 1, x);
dfs(y - 1, x);
dfs(y, x + 1);
dfs(y, x - 1);
}
}
}처음 제출할 땐 그래프 값을 받아올 때 split메서드를 사용했고
두번째 제출할 땐 StringTokenizer를 사용했다.
for (int i = 0; i < K; i++) {
String[] str = br.readLine().split(" ");
int y = Integer.parseInt(str[0]);
int x = Integer.parseInt(str[1]);
graph[y + 1][x + 1] = 1;
}
StringTokenizer가 살짝 더 빨랐다.
2580번: 스도쿠
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루
www.acmicpc.net
문제 요약 : 우리가 알고 있는 스도쿠 방식과 같다
위와 같은 그림에서 빈칸을 채우는데 같은 행,열에 같은 숫자가 들어갈 수 없고,
작은 3x3 사각형에도 같은 숫자가 들어갈 수 없다.
풀이 방식
첫칸부터 오른쪽으로 한칸씩 이동하며 해당 칸이 빈칸(0)이라면
chk메서드를 사용하여 1부터 9까지 어떤수가 적합한지 체크하여 입력한다.
chk메서드 에서는 3가지 조건을 확인한다.
1. 해당 행에서 같은 숫자가 있는지
2. 해당 열에서 같은 숫자가 있는지
3. 해당 칸이 포함된 3x3사각형에서 같은 숫자가 있는지
입력한 후 다음 빈칸을 찾아서 오른쪽으로 한칸 씩 이동한다.
오른쪽으로 이동하며 행의 끝까지 갔다면 다음 열로 이동하고 행의 인덱스를 처음으로 바꿔준다.
다음 빈칸에서 chk를 사용했는데 만족하는 수가 없다면
그 이전 칸을 잘못 입력한 것이므로 return 하여 이전 칸을 수정한다.
모든 칸을 입력했다면 출력한다.
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 스도쿠_2580_풀이1 {
static int[][] sdoku;
static int[][] mini;
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 주어진 스도쿠판
sdoku = new int[9][9];
for (int i = 0; i < 9; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < 9; j++) {
sdoku[i][j] = Integer.parseInt(st.nextToken());
}
}
// 빈칸에 1~9까지 입력
run(0, 0);
}
static void run(int y, int x) throws IOException {
//종료조건 모든 행렬을 다채웠을때
if (y == 9) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
bw.write(sdoku[i][j] + " ");
}
bw.newLine();
}
bw.flush();
bw.close();
System.exit(0);
}
//한 행을 다채우면 다음열로 넘어간다
if (x == 9) {
run(y + 1, 0);
return;
}
// 다채울때까지 아래 실행
// 해당칸이 빈칸이라면
if (sdoku[y][x] == 0) {
//해당칸에 둘 수 있는가 확인하기
for (int c = 1; c <= 9; c++) {
//해당칸을포함하는 작은 3*3 찾기
mini(y, x);
if (chk(y, x, c) == true) {
//만족하면 해당칸은 c로 두기
sdoku[y][x] = c;
//그 옆칸 실행
run(y, x + 1);
}
}
//해당칸에 둘 수 없다면
// 다시 해당칸을 0으로 만들고 그 전 칸 실행
sdoku[y][x] = 0;
return;
}
//해당칸이 빈칸이 아니라면 옆칸 실행
run(y, x + 1);
}
// 둘 수 있는 지 확인
static boolean chk(int y, int x, int c) {
// 1 행비교
for (int i = 0; i < 9; i++) {
if (sdoku[y][i] == c) {
return false;
}
}
// 2 열비교
for (int i = 0; i < 9; i++) {
if (sdoku[i][x] == c) {
return false;
}
}
// 3 미니비교(3x3)
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (mini[i][j] == c) {
return false;
}
}
}
// 놓을 수 있으면 t 없으면 f
return true;
}
// 미니생성
static void mini(int y, int x) {
mini = new int[3][3];
if (y < 3) {
if (x < 3) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
mini[i][j] = sdoku[i][j];
}
}
} else if (3 <= x && x < 6) {
for (int i = 0; i < 3; i++) {
for (int j = 3; j < 6; j++) {
mini[i][j - 3] = sdoku[i][j];
}
}
} else if (6 <= x && x < 9) {
for (int i = 0; i < 3; i++) {
for (int j = 6; j < 9; j++) {
mini[i][j - 6] = sdoku[i][j];
}
}
}
} else if (3 <= y && y < 6) {
if (x < 3) {
for (int i = 3; i < 6; i++) {
for (int j = 0; j < 3; j++) {
mini[i - 3][j] = sdoku[i][j];
}
}
} else if (3 <= x && x < 6) {
for (int i = 3; i < 6; i++) {
for (int j = 3; j < 6; j++) {
mini[i - 3][j - 3] = sdoku[i][j];
}
}
} else if (6 <= x && x < 9) {
for (int i = 3; i < 6; i++) {
for (int j = 6; j < 9; j++) {
mini[i - 3][j - 6] = sdoku[i][j];
}
}
}
} else if (6 <= x && x < 9) {
if (y < 3) {
for (int i = 6; i < 9; i++) {
for (int j = 0; j < 3; j++) {
mini[i - 6][j] = sdoku[i][j];
}
}
} else if (3 <= y && y < 6) {
for (int i = 6; i < 9; i++) {
for (int j = 3; j < 6; j++) {
mini[i - 6][j - 3] = sdoku[i][j];
}
}
} else if (6 <= y && y < 9) {
for (int i = 6; i < 9; i++) {
for (int j = 6; j < 9; j++) {
mini[i - 6][j - 6] = sdoku[i][j];
}
}
}
}
}
}처음에는 작은 3x3 사각형을 일일이 경우를 나눠서 구해줬었는데
인터넷 검색 후 더 좋은 방식을 알게됐다.
나눗셈을 이용하여 해당 칸을 구하는 방식이다.
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 스도쿠_2580_풀이2 {
static int[][] sdoku;
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 주어진 스도쿠판
sdoku = new int[9][9];
for (int i = 0; i < 9; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < 9; j++) {
sdoku[i][j] = Integer.parseInt(st.nextToken());
}
}
// 빈칸에 1~9까지 입력
run(0, 0);
}
static void run(int y, int x) throws IOException {
//종료조건 모든 행렬을 다채웠을때
if (y == 9) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
bw.write(sdoku[i][j] + " ");
}
bw.newLine();
}
bw.flush();
bw.close();
System.exit(0);
}
//한 행을 다채우면 다음열로 넘어간다
if (x == 9) {
run(y + 1, 0);
return;
}
// 다채울때까지 아래 실행
// 해당칸이 빈칸이라면
if (sdoku[y][x] == 0) {
//해당칸에 둘 수 있는가 확인하기
for (int c = 1; c <= 9; c++) {
if (chk(y, x, c) == true) {
//만족하면 해당칸은 c로 두기
sdoku[y][x] = c;
//그 옆칸 실행
run(y, x + 1);
}
}
//해당칸에 둘 수 없다면
//다시 해당칸을 0으로 만들고 그 전 칸 실행
sdoku[y][x] = 0;
return;
}
//해당칸이 빈칸이 아니라면 옆칸 실행
run(y, x + 1);
}
// 둘 수 있는 지 확인
static boolean chk(int y, int x, int c) {
// 1 행비교
for (int i = 0; i < 9; i++) {
if (sdoku[y][i] == c) {
return false;
}
}
// 2 열비교
for (int i = 0; i < 9; i++) {
if (sdoku[i][x] == c) {
return false;
}
}
// 3 미니비교(3x3)
int start_x = (x / 3) * 3 ; // c가 속한 3x3의 행의 첫 위치
int start_y = (y / 3) * 3 ; // c가 속한 3x3의 열의 첫 위치
for (int i = start_y; i < start_y + 3; i++) {
for (int j = start_x; j < start_x + 3; j++) {
if (sdoku[i][j] == c) {
return false;
}
}
}
// 놓을 수 있으면 t 없으면 f
return true;
}
}처음 내가 작성한 코드의 실행 결과는
수정한 코드의 실행결과는
와 같다.