[백준] 2578번 : 빙고 - 자바[Java]

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

2578번: 빙고

 

풀이

5X5 배열을 만들고 배열에 값을 채워 넣은 다음, 숫자를 입력할 때마다 모든 행/열/대각선을 탐색하여 빙고가 되는지 체크한다.

3줄 빙고가 완성된다면 그 위치를 answer에 저장하고, 모든 입력이 끝난 다음 출력한다.

 

전역 변수 및 지역 변수 설명

• int[5][5] arr : 빙고 배열
• boolean[5][5] flag : 사회자가 부른 수가 빙고에 있으면 해당 위치를 true로 변경
• 이미 빙고가 된 행, 열, 대각선을 중복 체크하지 않기 위해 다음 변수를 전역 변수로 선언 
  • boolean[5] rowBingo : i번 행이 빙고가 되어있으면 rowBingo[i] = true
  • boolean[5] colBingo : j번 열이 빙고가 되어있으면 colBingo[j] =  true
  • boolean[2] crossBingo : 왼쪽에서 오른쪽으로 내려가는 대각선/오른쪽에서 왼쪽으로 내려가는 대각선이 빙고라면 각각 crossBingo[0] = true, crossBingo[1] = true
• int cnt : 빙고가 된 횟수
• int answer : 출력할 답

 

void find(int num, int[][] arr, boolean[][] flag) : arr에서 num의 위치를 찾는 함수

	public static void find(int num, int[][] arr, boolean[][] flag) {
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				if (arr[i][j] == num) {
					flag[i][j] = true;
					return;
				}
			}
		}
	}

배열을 탐색하다 num을 찾으면 flag[i][j] = true하고 return

 

void cal(boolean[][] flag, int idx) : 빙고가 되는지 체크하는 함수

	public static void cal(boolean[][] flag) {
		
		// 행 탐색
		for (int i = 0; i < 5; i++) {
			boolean check = true;
			
			if (rowBingo[i]) continue;
			
			for (int j = 0; j < 5; j++) {
				if (!flag[i][j]) {
					check = false;
					break;
				}
			}
			
			if (check) {
				rowBingo[i] = true;
				cnt++;
				if (cnt == 3)
					return;
			}
		}
		
		//열 탐색
		for (int j = 0; j < 5; j++) {
			boolean check = true;
			
			if (colBingo[j]) continue;
			
			for (int i = 0; i < 5; i++) {
				if (!flag[i][j]) {
					check = false;
					break;
				}
			}
			
			if (check) {
				colBingo[j] = true;
				cnt++;
				if (cnt == 3)
					return;
			}
		}
		
		//대각선 탐색
		boolean check = true;
		for (int i = 0, j = 0; i < 5; i++, j++) {
			
			if (crossBingo[0]) break;
			
			if (!flag[i][j]) {
				check = false;
				break;
			}
			
		}
		
		if (check && !crossBingo[0]) {
			crossBingo[0] = true;
			cnt++;
			if (cnt == 3)
				return;
		}
		
		check = true;
		for (int i = 0, j = 4; i < 5; i++, j--) {
			
			if (crossBingo[1]) break;
			
			if (!flag[i][j]) {
				check = false;
				break;
			}
			
		}
		if (check && !crossBingo[1]) {
			crossBingo[1] = true;
			cnt++;
			if (cnt == 3)
				return;
		}
		
	}

모든 행, 모든 열, 두 개의 대각선이 빙고가 되는지 체크하고

빙고가 된다면 cnt에 1을 더하고 만약 cnt가 3이라면 바로 함수를 종료한다.

코드

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

public class Main {
	
	static boolean[] rowBingo = new boolean[5];
	static boolean[] colBingo = new boolean[5];
	static boolean[] crossBingo = new boolean[2];
	static int cnt = 0;
	
	public static void cal(boolean[][] flag) {
		
		// 행 탐색
		for (int i = 0; i < 5; i++) {
			boolean check = true;
			
			if (rowBingo[i]) continue;
			
			for (int j = 0; j < 5; j++) {
				if (!flag[i][j]) {
					check = false;
					break;
				}
			}
			
			if (check) {
				rowBingo[i] = true;
				cnt++;
				if (cnt == 3)
					return;
			}
		}
		
		//열 탐색
		for (int j = 0; j < 5; j++) {
			boolean check = true;
			
			if (colBingo[j]) continue;
			
			for (int i = 0; i < 5; i++) {
				if (!flag[i][j]) {
					check = false;
					break;
				}
			}
			
			if (check) {
				colBingo[j] = true;
				cnt++;
				if (cnt == 3)
					return;
			}
		}
		
		//대각선 탐색
		boolean check = true;
		for (int i = 0, j = 0; i < 5; i++, j++) {
			
			if (crossBingo[0]) break;
			
			if (!flag[i][j]) {
				check = false;
				break;
			}
			
		}
		
		if (check && !crossBingo[0]) {
			crossBingo[0] = true;
			cnt++;
			if (cnt == 3)
				return;
		}
		
		check = true;
		for (int i = 0, j = 4; i < 5; i++, j--) {
			
			if (crossBingo[1]) break;
			
			if (!flag[i][j]) {
				check = false;
				break;
			}
			
		}
		if (check && !crossBingo[1]) {
			crossBingo[1] = true;
			cnt++;
			if (cnt == 3)
				return;
		}
		
	}
	
	public static void find(int num, int[][] arr, boolean[][] flag) {
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				if (arr[i][j] == num) {
					flag[i][j] = true;
					return;
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[][] arr = new int[5][5];
		boolean[][] flag = new boolean[5][5];
		
		for (int i = 0; i < 5; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 5; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int answer = 0;
		
		for (int i = 0; i < 5; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < 5; j++) {
				int num = Integer.parseInt(st.nextToken());
				
				if (cnt == 3) continue;
				
				find(num, arr, flag);
				cal(flag);
				if (cnt == 3) {
					answer = i*5 + j+1;
				}
			}
		}
		
		System.out.println(answer);
		
	}

}

---

다른 풀이 2

cal 함수에서 매번 숫자를 입력할 때마다 모든 행, 열, 대각선을 체크하는 것은 비효율적이다. 그래서 입력받은 숫자의 위치에 해당하는 행, 열, 대각선만 탐색하여 빙고가 되는지 체크한다.

 

이 때 입력받은 숫자의 위치를 find에서 찾아 반환한 값을 cal에 매개변수로 넘겨야 하는데

두 개의 변수를 한꺼번에 return 받기 위해 find 함수에서 (10*i + j )를 리턴하여 행의 위치는 십의 자리, 열의 위치는 일의 자리 숫자가 되게 하여 return 한다. 이 방법은 배열의 인덱스가 9이하이기 때문에 가능하다.

 

기본적인 로직은 위의 풀이와 같다.

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

public class Main {
	
	static boolean[] rowBingo = new boolean[5];
	static boolean[] colBingo = new boolean[5];
	static boolean[] crossBingo = new boolean[2];
	static int cnt = 0;
	
	public static void cal(boolean[][] flag, int idx) {
		int row = idx / 10;
		int col = idx % 10;
		
		// 행 탐색
		
		boolean check = true;
			
		if (!rowBingo[row]) {
			
			for (int j = 0; j < 5; j++) {
				if (!flag[row][j]) {
					check = false;
					break;
				}
			}
			
			if (check) {
				rowBingo[row] = true;
				cnt++;
				if (cnt == 3)
					return;
			}
		}
		
		//열 탐색
		check = true;
			
		if (!colBingo[col]) {
			
			for (int i = 0; i < 5; i++) {
				if (!flag[i][col]) {
					check = false;
					break;
				}
			}
			
			if (check) {
				colBingo[col] = true;
				cnt++;
				if (cnt == 3)
					return;
			}
		}
		
		// 대각선 탐색
		// 왼쪽에서 오른쪽으로 내려가는 대각선
		check = true;
		if ( row == col) {
			for (int i = 0, j = 0; i < 5; i++, j++) {
			
				if (crossBingo[0]) break;
			
				if (!flag[i][j]) {
					check = false;
					break;
				}
			
			}
			
			if (check && !crossBingo[0]) {
				crossBingo[0] = true;
				cnt++;
				if (cnt == 3)
					return;
			}
		}
		
		// 오른쪽에서 왼쪽으로 내려가는 대각선
		check = true;
		if (row + col == 4) {
			for (int i = 0, j = 4; i < 5; i++, j--) {
			
				if (crossBingo[1]) break;
			
				if (!flag[i][j]) {
					check = false;
					break;
				}
			
			}
			if (check && !crossBingo[1]) {
				crossBingo[1] = true;
				cnt++;
				if (cnt == 3)
					return;
			}
		}
		
	}
	
	public static int find(int num, int[][] arr, boolean[][] flag) {
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				if (arr[i][j] == num) {
					flag[i][j] = true;
					return 10*i + j;
				}
			}
		}
		
		return -1;
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[][] arr = new int[5][5];
		
		boolean[][] flag = new boolean[5][5]; // 이거 안 쓰고 그냥 arr[][] = -1이나 0으로 바꾸면 됨
		
		for (int i = 0; i < 5; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 5; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int answer = 0;
		
		for (int i = 0; i < 5; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < 5; j++) {
				int num = Integer.parseInt(st.nextToken());
				
				if (cnt == 3) continue;
				
				int idx = find(num, arr, flag);
				cal(flag, idx);
				if (cnt == 3) {
					answer = i*5 + j+1;
				}
			}
		}
		
		System.out.println(answer);
		
	}

}