[백준/python] 2234번 성

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

 

 

코드

# 성곽
# 복습 횟수:2, 01:30:00, 복습필요O
import sys
from collections import deque
si = sys.stdin.readline 
M, N = map(int, si().split())

# 가려는 방향에도 벽이 있는지를 체크해야한다. 북남서동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
tmp_list = []

for i in range(N):
    tmp_list.append(list(map(int, si().split())))

graph = [[[] for i in range(M)]for i in range(N)]

def converter(i, j):
    val = tmp_list[i][j]
    tmp = []
    while val:
        rst = val % 2
        tmp.append(rst)
        val = val // 2
    
    while len(tmp) != 4:
        tmp.append(0)
    
    tmp.reverse()
        
    graph[i][j] = tmp[:]
    return

for i in range(N):
    for j in range(M):
        converter(i, j)

visited = [[0 for i in range(M)] for i in range(N)]

# 2. 완탐
team_flag = 1 
maxi = -1
    
def bfs(x, y):
    global maxi
    q = deque()
    q.append([x, y])
    visited[x][y] = team_flag
    check_num = 0
    while q:
        x, y = q.popleft()
        check_num += 1 

        for i in range(4): # 북남서동
            nx, ny = x + dx[i], y + dy[i]
            if not (0 <= nx < N and 0 <= ny < M): continue # 격자점을 벗어난다면
            if visited[nx][ny]: continue # 방문한 경우였다면 continue
            if not checkMyWall(x, y, i): continue # 내쪽에서 가려는 방향에 벽이 있다면 continue
            if not checkNextWall(nx, ny, i): continue # 가려는 쪽에서 내쪽으로 벽이 있다면 continue

            q.append([nx, ny])
            visited[nx][ny] = team_flag  # 방문처리


    maxi = max(maxi, check_num)
    return
def checkNextWall(nx, ny, i):
    wall_list = graph[nx][ny]
    if i == 0: # 남쪽
        if wall_list[0]:
            return False
        else:
            return True
    elif i == 1: # 북쪽
        if wall_list[2]:
            return False
        else:
            return True
    elif i == 2: # 동쪽
        if wall_list[1]:
            return False
        else:
            return True
    else: # 서쪽
        if wall_list[3]:
            return False
        else:
            return True

def checkMyWall(x, y, i):
    wall_list = graph[x][y]

    if i == 0: # 북쪽
        if wall_list[2]:
            return False
        else:
            return True
    elif i == 1: # 남쪽
        if wall_list[0]:
            return False
        else:
            return True 
    elif i == 2: # 서쪽
        if wall_list[3]:
            return False
        else: 
            return True
    else: # 동쪽
        if wall_list[1]:
            return False
        else:
            return True

for i in range(N):
    for j in range(M):
        if visited[i][j] == 0:
            bfs(i, j)
            team_flag += 1

print(team_flag-1)
print(maxi)

# 합쳐졌을 때 더 커지는 케이스
case_set = set()

for i in range(N):
    for j in range(M):
        me = visited[i][j]
        for idx in range(4):
            ni, nj = i + dx[idx], j + dy[idx]

            if not (0 <= ni < N and 0 <= nj < M): continue # 격자 밖 continue

            if visited[ni][nj] != me:
                tmp_list = sorted([me, visited[ni][nj]])
                case_set.add(tuple(tmp_list))

total_maxi = maxi
for home, away in case_set:
    tmp = 0
    for i in range(len(visited)):
        for j in range(len(visited[0])):
            if visited[i][j] == home or visited[i][j] == away:
                tmp += 1
    total_maxi = max(total_maxi, tmp)

print(total_maxi)

풀이

1. 인접한 곳끼리 각각의 그룹을 이루므로 team_flag를 두어 구분합니다.

2. 방문처리를 할 때 기존처럼 0, 1로 구분하는 것이 아니라 team_flag로 하여

 각각의 팀을 구분합니다.

3.  bfs 한번에 갈 수있는 방의 팀을 모두 구할 수 있으므로  bfs()에 check_num 변수를 두어

방의 개수를 체크합니다.

4. 갈 수 있는 방을 체크하기 위해서는 2개를 체크해야합니다.

첫번째로 본인의 방을 기준으로 벽을 고려해야합니다.

두번째로 가려는 방을 기준으로 병을 고려해야 합니다.

이 것이 바로 이 문제의 포인트라고 할 수 있습니다.