[백준 10026] 적록색약 (with Python / BFS)

문제링크

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

10026번: 적록색약

 

문제설명

 

문제풀이

1차시기 코드

큐에 삽입할 때 좌표와, 구역번호를 매겨 삽입하여 숫자를 세보려고 했다.

현재 좌표에서 다음 좌표 탐색할때 

같은 색상이면, section 넘버를 그대로 삽입,

다른 색상이면, section넘버 +1 늘려 삽입하며

BFS를 하면 그리드 판의 구역별로 넘버가 나눠져있어

가장 큰 숫자를 구하면 구역 개수를 구할 수 있을 거라는 멍청한 생각을 했다..

 

상하좌우 탐색시 다른색상이면 전부 section += 1 하므로 옳은 생각이 아니었음

from collections import deque

N = int(input())
graph = [[0 for _ in range(N)] for _ in range(N)]
section = [[0 for _ in range(N)] for _ in range(N)]
maxValue = 0

# 인풋값으로 그리드 판 채우기
for i in range(N):
    graph[i] = list(input())

def BFS(cur):
    global section
    queue = deque()
    queue.append(cur)

    while queue:
        (curX, curY), sNum = queue.popleft()
        section[curX][curY] = sNum

        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]

        # 다음 next좌표를 상하좌우로 찾는 로직
        for i in range(4):
            nx = curX + dx[i]
            ny = curY + dy[i]

            # section 리스트 값이 0이 아니면 방문한 것이므로 건너뜀
            # 즉 0이 아닌 수로 업데이트가 안된 좌표만 탐색.
            if 0 <= nx <= N-1 and 0 <= ny <= N-1 and not section[nx][ny]:
                # 값(색상)이 다르면 구역나누기 => sNum 값 1증가
                if graph[nx][ny] != graph[curX][curY]:
                    queue.append(((nx, ny), sNum + 1))
                # 값이 같으면 섹션넘버 그대로 가져감
                else:
                    queue.append(((nx, ny), sNum))
                    
BFS(((0, 0), 1))
print(section)

for row in section:
    rowMax = max(row)
    maxValue = max(maxValue, rowMax)

print(maxValue)

2차 시기 코드

아래와 같이 구현하니 시간초과 났다.

찾아보니 방법은 맞게 접근하였지만, 시간초과 문제가 해결이 안돼서

setrecursionlimit도 설정하고.. 여러가지 해보았지만 여전히 시간초과가 난다.

사실 주어질 수 있는 입력값 N이 100까지 범위라 N^2 해도 시간복잡도 상으로는 괜찮다는걸 알고 있었지만 말이다.

 

from collections import deque
import sys

sys.setrecursionlimit(1000000)
input = sys.stdin.readline
N = int(input())
graph = [0] * N
visited = [[False for _ in range(N)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 인풋값으로 그리드 판 채우기
for i in range(N):
    graph[i] = list(input())

def BFS(start):
    queue = deque([start])

    while queue:
        curX, curY = queue.popleft()
        visited[curX][curY] = True
        # 다음 next좌표를 상하좌우로 찾는 로직
        for i in range(4):
            nx = curX + dx[i]
            ny = curY + dy[i]

            # 인덱스 범위안에 있고 방문하지 않은 좌표이면 탐색
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                # 같은 색상이면 
                if graph[curX][curY] == graph[nx][ny]:
                    queue.append((nx, ny))

# BFS 활용하여 적록색약이 아닌 사람이 보는 section수 출력 로직
cnt1 = 0

for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            BFS((i, j))
            cnt1 += 1

# BFS 활용하여 적록색약인 사람이 보는 section수 출력 로직   
cnt2 = 0
visited = [[False for _ in range(N)] for _ in range(N)]

for i in range(N):
    for j in range(N):
        if graph[i][j] == 'G':
            graph[i][j] = 'R'

for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            BFS((i, j))
            cnt2 += 1

print(cnt1, cnt2)

 

코드

마지막으로 BFS호출하는 횟수가 여러번 있을거니까

그 안에서 visited 체크하는 로직에서 고칠 수 있겠다 싶어 보니,

이전 시기에는 큐에서 꺼낼때 visited체크 로직을 수행했지만,

큐에 삽입하고 나서 방문체크를 해야 중복된 노드를 탐색하지 않겠구나 싶어 수정하였다.

 

결과적으로 sys.stdin.readline 과 setlimitrecursion 처리 안해줘도 시간초과없이 성공!

 

정답코드

from collections import deque

N = int(input())
graph = [0] * N
visited = [[False for _ in range(N)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 인풋값으로 그리드 판 채우기
for i in range(N):
    graph[i] = list(input())

def BFS(x, y):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True

    while queue:
        curX, curY = queue.popleft()
        # 다음 next좌표를 상하좌우로 찾는 로직
        for i in range(4):
            nx = curX + dx[i]
            ny = curY + dy[i]

            # 인덱스 범위안에 있고 방문하지 않은 좌표이면 탐색
            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                # 같은 색상이면 
                if graph[curX][curY] == graph[nx][ny]:
                    queue.append((nx, ny))
                    visited[nx][ny] = True

# BFS 활용하여 적록색약이 아닌 사람이 보는 section수 출력 로직
cnt1 = 0

for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            BFS(i, j)
            cnt1 += 1

# BFS 활용하여 적록색약인 사람이 보는 section수 출력 로직   
cnt2 = 0
visited = [[False for _ in range(N)] for _ in range(N)]

for i in range(N):
    for j in range(N):
        if graph[i][j] == 'G':
            graph[i][j] = 'R'

for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            BFS(i, j)
            cnt2 += 1

print(cnt1, cnt2)