[Baekjoon] 9518_로마 카톨릭 미사

문제(출처: https://www.acmicpc.net/problem/9518)

---

< 로마 카톨릭 미사 >

 

문제 풀이 

 

빈자리 중 가장 많은 이웃이 있는 위치 + 사람이 앉아있는 자리의 이웃 수 (중복 x)

 

 my solution (Java)

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

public class _9518_ { // 로마 카톨릭 미사

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int R = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());

		char arr[][] = new char[R][S];
		for (int i = 0; i < R; i++) {
			String str = bf.readLine();
			for (int j = 0; j < S; j++) {
				arr[i][j] = str.charAt(j);
			}
		}

		int max = 0, result = 0;
		boolean visited[][] = new boolean[R][S];
		int dx[] = { -1, 1, 0, 0, -1, -1, 1, 1 };
		int dy[] = { 0, 0, -1, 1, -1, 1, -1, 1 };

		for (int i = 0; i < R; i++) {
			for (int j = 0; j < S; j++) {
				if (arr[i][j] == 'o') {
					visited[i][j] = true;
					for (int k = 0; k < 8; k++) {
						int x = i + dx[k];
						int y = j + dy[k];
						if (x >= 0 && x < R && y >= 0 && y < S && arr[x][y] == 'o' && !visited[x][y]) {
							result += 1;
						}
					}
					continue;
				}
				int cnt = 0;
				for (int k = 0; k < 8; k++) {
					int x = i + dx[k];
					int y = j + dy[k];
					if (x >= 0 && x < R && y >= 0 && y < S && arr[x][y] == 'o') {
						cnt += 1;
					}
				}
				if (cnt > max) {
					max = cnt;
				}
			}
		}
		System.out.println(result + max);
	}
}

변수)
R, S : 행, 열
arr : 사람의 배치
max, result : 빈자리 중에서 악수할 수 있는 최댓값, 이미 앉아있는 사람의 악수 횟수
visited : 악수 여부
dx, dy : 이웃

 

행, 열을 입력받는다. 사람의 배치 정보를 입력받아 arr에 저장한다. arr을 전체 탐색한다.

 

1) 사람이 앉아있는 자리라면 악수 여부를 true로 저장한 후 인접한 칸 여덟 칸을 살펴보며 이웃 중 악수하지 않은 사람의 수를 센다.

2) 빈자리라면 인접한 칸 여덟 칸을 살펴보며 이웃의 수를 센다. max를 최댓값으로 업데이트한다.

 

최종 result와 max의 합을 출력한다.

---

---