[BOJ]2234 성곽

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

2234번: 성곽

풀이

오랜만의 그래프 문제다. 오늘 막 AI Tech 4기 신청서를 냈다. 준비가 안된 상태에서 작성하고 낸 것 같아서 마음이 무겁지만, 그래도 도전해볼려고 한다. 일단 프리코스는 진작에 다 수강하였고 계속해서 코테와 AI ML 기본 공부를 하고 있다. ML 공부는 정말이지 기초만 배워도 어려운 것 같다. 여러 가지 강의와 책을 보고 있지만 참 쉽지 않다. 이 문제는 아주 전형적인 유형이었던 것 같다. 먼저 방의 갯수, 최대 방의 크기는 굉장히 흔한 문제이다. 단순히 queue 자료구조를 이용하여 BFS로 탐색하며 방문 처리를 해주고, 각 경우에 대하여 최대 크기만 구하면 된다. 문제는 3번째 답이다. 벽을 하나 부셨을 때 최대 크기라니... 예전에 연구소2였나 하는 문제에서 벽 부스는거에 벽을 느껴서 선뜻 나서기 어려웠다. 그러나 한번 풀어본 짬바가 있었는지 금방 해답을 구하였다. 먼저 모든 칸에 대하여 벽 4개에 대한 부셨는지 여부를 저장하는 wall_visited을 선언해주었다. 그 다음 벽을 부쉈는지 여부를 확인하기 위해 break_flag를 선언해주고, 만약 벽을 만나면, 또한 벽을 부수지 않았다면, 만약 이 벽이 부숴진 적이 없다면 벽을 부수는 알고리즘을 구현하였다. 다행히 벽을 한번만 부술 수 있어서 그나마 나았던 것 같다. n번 부술 수 있다고 하면 문제가 복잡해진다.

import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()
m, n = map(int, input().split())
#a = format(15, 'b')
wall = [[[0, 0, 0, 0]for _ in range(m)]for _ in range(n)]
input_mtr = [list(map(int, input().split()))for _ in range(n)]
for i in range(n):
    for j in range(m):
        binary = format(input_mtr[i][j], 'b')
        for k in range(len(binary)-1, -1, -1):
            if binary[len(binary)-k-1] == '1':
                wall[i][j][k] = 1
dx = [0, -1, 0, 1]
dy = [-1, 0, 1, 0]
visited = [[False for _ in range(m)]for _ in range(n)]
wall_visited = [[[False for _ in range(4)] for _ in range(m)]for _ in range(n)]
max_room = 0
wall_break_max = 0
room_num = 0
for i in range(n):
    for j in range(m):
        if not visited[i][j]: #벽을 부수지 않았을 떄 방 갯수와 최대 크기
            q = deque()
            q.append([i, j])
            visited[i][j] = True
            tempt_area = 1
            while q:
                x, y = q.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if nx < 0 or ny < 0 or nx >= n or ny >= m:
                        continue
                    if wall[x][y][k] == 1:
                        continue
                    if visited[nx][ny]:
                        continue
                    q.append([nx, ny])
                    visited[nx][ny] = True
                    tempt_area += 1
            if max_room < tempt_area:
                max_room = tempt_area
            room_num += 1
        break_flag= False
        wall_break_visited = [[False for _ in range(m)]for _ in range(n)]
        wall_break_visited[i][j] = True
        tempt_break_area = 1
        q = deque()
        q.append([i, j])
        while q:
            x, y = q.popleft()
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
                if nx< 0 or ny <0 or nx>=n or ny >= m:
                    continue
                if not wall_break_visited[nx][ny]:
                    if wall[x][y][k] == 1:
                        if not break_flag:
                            if not wall_visited[x][y][k]:
                                    wall_visited[x][y][k] = True
                                    break_flag = True
                                    q.append([nx, ny])
                                    wall_break_visited[nx][ny] = True
                                    tempt_break_area +=  1
                    else:
                        q.append([nx, ny])
                        wall_break_visited[nx][ny] = True
                        tempt_break_area +=  1
        if wall_break_max < tempt_break_area:
            wall_break_max = tempt_break_area
print(room_num, max_room, wall_break_max, sep="\n")