백준 1388 바닥 장식 (Java,자바)

jonghyukLee·2022년 8월 23일
0

이번에 풀어본 문제는
백준 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;
    }
}

📝 풀이

가로, 세로로 서로 길이만 다른 모양의 타일이 있을 때, 같은 모양의 타일이 이어진 경우는 하나의 타일이라고 가정합니다.
주어진 입력에서 총 몇 개의 타일이 사용된 지 출력하는 문제입니다.
가로 세로 일직선으로의 탐색을 통해 간단하게 해결할 수 있습니다.

📜 후기

최근 프로젝트를 하며 시간관리가 잘 안돼서, 알고리즘에 비중을 너무 못두는 것 같습니다 ㅠ 최근에 스터디를 하나 새로 시작했는데, 이번 스터디를 통해 강제로라도 꾸준히 문제를 풀어갈 생각입니다!

profile
머무르지 않기!

0개의 댓글