이번에 풀어본 문제는
백준 1388번 바닥 장식 입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Wood
{
int x,y;
public Wood(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int N,M;
static char [][] map;
static boolean [][] isVisited;
static int [] dx = {0,1}; // 우 , 하
static int [] dy = {1,0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N][M];
isVisited = new boolean[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
map[i] = st.nextToken().toCharArray();
}
int answer = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if(!isVisited[i][j]) {
answer++;
// 가로 판자일 때,
if (map[i][j] == '-') {
bfs(i, j, 0);
}
else bfs(i, j, 1);
}
}
}
System.out.print(answer);
}
static void bfs(int i, int j, int dir) {
Queue<Wood> q = new LinkedList<>();
q.add(new Wood(i,j));
char curShape = map[i][j];
while(!q.isEmpty()) {
Wood cur = q.poll();
//한칸 이동
int mx = cur.x + dx[dir];
int my = cur.y + dy[dir];
if (!isValid(mx, my) || isVisited[mx][my] || map[mx][my] != curShape) continue;
isVisited[mx][my] = true;
q.add(new Wood(mx, my));
}
}
static boolean isValid(int x, int y) {
return x >= 0 && y >= 0 && x < N && y < M;
}
}
가로, 세로로 서로 길이만 다른 모양의 타일이 있을 때, 같은 모양의 타일이 이어진 경우는 하나의 타일이라고 가정합니다.
주어진 입력에서 총 몇 개의 타일이 사용된 지 출력하는 문제입니다.
가로 세로 일직선으로의 탐색을 통해 간단하게 해결할 수 있습니다.
최근 프로젝트를 하며 시간관리가 잘 안돼서, 알고리즘에 비중을 너무 못두는 것 같습니다 ㅠ 최근에 스터디를 하나 새로 시작했는데, 이번 스터디를 통해 강제로라도 꾸준히 문제를 풀어갈 생각입니다!