문제
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc&categoryId=AV5LwsHaD1MDFAXc&categoryType=CODE&problemTitle=%ED%8C%8C%ED%95%91%ED%8C%8C%ED%95%91&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1
Java 풀이
import java.util.*;
import java.lang.*;
import java.io.*;
class Tuple{
private int first;
private int second;
public Tuple(int first,int second){
this.first=first;
this.second=second;
}
public int getFirst(){
return this.first;
}
public int getSecond(){
return this.second;
}
}
// The main method must be in a class named "Main".
class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int tc=sc.nextInt();
int[] dx={0,0,-1,1,-1,-1,1,1};
int[] dy={-1,1,0,0,1,-1,1,-1};
for(int i=1;i<=tc;i++){
int answer=0;
int n=sc.nextInt();
String[][] board=new String[n][n];
int[][] bomb_checker=new int[n][n];
boolean[][] visited=new boolean[n][n];
for(int j=0;j<n;j++){
String s=sc.next();
for(int k=0;k<n;k++){
board[j][k]=Character.toString(s.charAt(k));
}
}
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
if(board[j][k].equals("*")){
bomb_checker[j][k]=-1;
}else{
int cnt=0;
for(int m=0;m<8;m++){
int nx=j+dx[m];
int ny=k+dy[m];
if(nx<0 || ny<0 || nx>=n || ny>=n){
continue;
}
if(board[nx][ny].equals("*")){
cnt++;
}
}
bomb_checker[j][k]=cnt;
}
}
}
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
if(bomb_checker[j][k]==0 && !visited[j][k]){
answer++;
visited[j][k]=true;
Queue<Tuple> q=new LinkedList<>();
q.offer(new Tuple(j,k));
while(!q.isEmpty()){
Tuple tuple=q.poll();
int x=tuple.getFirst();
int y=tuple.getSecond();
if(bomb_checker[x][y]>0){
continue;
}
for(int m=0;m<8;m++){
int nx=x+dx[m];
int ny=y+dy[m];
if(nx<0||ny<0||nx>=n||ny>=n){
continue;
}
if(visited[nx][ny]){
continue;
}
if(bomb_checker[nx][ny]==-1){
continue;
}
if(m>=4){
if(!visited[nx][y] || !visited[x][ny]){
continue;
}
}
visited[nx][ny]=true;
q.offer(new Tuple(nx,ny));
}
}
}
}
}
for(int j=0;j<n;j++){
for(int k=0;k<n;k++){
if(!visited[j][k] && bomb_checker[j][k]>0){
answer++;
}
}
}
System.out.printf("#%d %d\n",i,answer);
}
}
}
내 생각
- 각 보드에서 폭탄과 폭탄이 아닌 칸이 구분되어 있고 폭탄이 아닌 칸을 최소한으로 눌러야 하므로 최대한 많은 주위의 폭탄이 없는 0인 칸을 눌러서 주변에 0인 칸과 0과 폭탄이 아닌 칸이 드러나게 해야한다. 그렇기 때문에 보드에서 주변의 폭탄의 수를 세서 숫자를 기록하고 0인 칸부터 눌러서 BFS를 통해 칸이 들어나게 한 후, 해당이 되지 않는 나머지 케이스, 즉 0을 눌렀을 때, 들어나지 않으면서 폭탄도 아닌 숫자(한칸에 하나씩 밖에 들어나지 않는 칸)을 세어 더해주면 된다.
- BFS를 위해 튜플이 필요하여 자바에는 없는 Tuple 클래스를 따로 생성해서 큐에 값을 넣고 뺄 수 있게 하였다.
- 중간에 문자열과 문자를 비교할 때, 를 ""가 아닌 '*'로 둘러싸서 문자로 인식되는걸 찾느라 시간이 좀 걸렸다.
- 풀이시간 : 50분
Python 풀이
import copy
from collections import deque
for tc in range(int(input())):
n=int(input())
board=[]
dx=[0,0,-1,1,-1,-1,1,1]
dy=[-1,1,0,0,-1,1,-1,1]
for i in range(n):
board.append(list(input()))
bomb_checker=[[0]*n for _ in range(n)]
for i in range(n):
for j in range(n):
if board[i][j]=='*':
bomb_checker[i][j]=-1
continue
cnt=0
for k in range(8):
nx=i+dx[k]
ny=j+dy[k]
if nx<0 or ny<0 or nx>=n or ny>=n:
continue
if board[nx][ny]=='*':
cnt+=1
bomb_checker[i][j]=cnt
answer=0
visited=[[False]*n for _ in range(n)]
for i in range(n):
for j in range(n):
if bomb_checker[i][j]==0 and not visited[i][j]:
q=deque([])
q.append((i,j))
visited[i][j]=True
answer+=1
while q:
x,y=q.popleft()
if bomb_checker[x][y]>0:
continue
for k in range(8):
nx=x+dx[k]
ny=y+dy[k]
if nx<0 or ny<0 or nx>=n or ny>=n:
continue
if visited[nx][ny]:
continue
if bomb_checker[nx][ny]==-1:
continue
if k>=4:
if not visited[x][ny] or not visited[nx][y]:
continue
visited[nx][ny]=True
q.append((nx,ny))
for i in range(n):
for j in range(n):
if bomb_checker[i][j]>0 and not visited[i][j]:
answer+=1
print("#"+str(tc+1)+" "+str(answer))
내 생각
