코딩 테스트 스터디/백준

[골드 V] 10026번. 적록색약

남쪽마을밤송이 2022. 9. 17. 21:53

 문제 

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

 

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

 사용 언어 

Python3

 풀이 과정 

오랜만에 그래프 탐색다운 그래프 탐색 문제를 풀었다.

기본적인듯 생각해야 해서 처음엔 고민 좀 했다가 감은 잡았는데 list랑 함수를 재활용하려다가 엄청 꼬였다...ㅎㅎ 그래서 스터디 팀원들과도 고민해봤는데 재활용하기에 좋은 문제는 아닌 것 같다는 판단을 내리고 오늘 처음부터 다시 풀었다.

from collections import deque
from sys import stdin
input = stdin.readline

def bfs(type, x, y, visited):
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    q = deque([(x, y)])
    if type == "normal":
        visited[x][y] = True
    else:
        visited[x][y] = False
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            # 인덱스 범위 안에 있으면서, 같은 색이면서, 방문 안한 경우
            if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == graph[x][y]:
                if type == "normal":
                    if not visited[nx][ny]:
                        visited[nx][ny] = True  # 방문체크 후 큐에 넣음
                        q.append((nx, ny))
                        if graph[nx][ny] == "G":
                            print(nx, ny)
                            graph[nx][ny] = "R"
                else:
                    if visited[nx][ny]:
                        visited[nx][ny] = False  # 방문체크 후 큐에 넣음
                        q.append((nx, ny))

if __name__ == "__main__":
    N = int(input())
    graph = [list(input().strip()) for _ in range(N)]
    visited = [[False] * N for _ in range(N)]
    
    normal = 0
    for i in range(N):
        for j in range(N):
            if visited[i][j] == False:
                bfs("normal", i, j, visited)
                normal += 1

    colorless = 0
    print(graph)
    for i in range(N):
        for j in range(N):
            if visited[i][j] == True:
                bfs("colorless", i, j, visited)
                colorless += 1

    print(normal, colorless)

시도했던 코드를 남겨두는데 이 코드의 제일 큰 문제는 처음 정상적인 사람의 경우를 돌면서 다음번 색맹인 사람을 위해 그래프를 바꿔두려 했는데 그랬더니 값이 이상해지는 것 같았다... 그거 말고도 경우를 한 번 더 나눠야 해서 좀 비효율적이었다.

 

어쨌든 정석 bfs 방식으로 풀고 맞았습니다!!

 

 제출 답안 

from collections import deque
from sys import stdin
input = stdin.readline

def BFS(x, y):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    q = deque([(x, y)])
    visited[x][y] = True
    while q:
        cx, cy = q.popleft()
        for d in range(4):
            nx = cx + dx[d]
            ny = cy + dy[d]
            if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == False:
                if graph[cx][cy] == graph[nx][ny]:
                    visited[nx][ny] = True
                    q.append((nx, ny))

def colorChange(graph):
    for i in range(N):
        for j in range(N):
            if graph[i][j] == "G":
                graph[i][j] = "R"
    return graph

if __name__ == "__main__":
    N = int(input())
    graph = [list(input().strip()) for _ in range(N)]
    
    visited = [[False] * N for _ in range(N)]
    normal = 0
    for i in range(N):
        for j in range(N):
            if visited[i][j] == False:
                BFS(i, j)
                normal += 1
    
    graph = colorChange(graph)
    visited = [[False] * N for _ in range(N)]
    colorless = 0
    for i in range(N):
        for j in range(N):
            if visited[i][j] == False:
                BFS(i, j)
                colorless += 1

    print(normal, colorless)

 

 코드 개선 

1. 궁금해서 graph와 visited도 함수의 지역 변수로 돌려보았다.

from collections import deque
from sys import stdin
input = stdin.readline

def BFS(x, y, graph, visited):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    q = deque([(x, y)])
    visited[x][y] = True
    while q:
        cx, cy = q.popleft()
        for d in range(4):
            nx = cx + dx[d]
            ny = cy + dy[d]
            if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == False:
                if graph[cx][cy] == graph[nx][ny]:
                    visited[nx][ny] = True
                    q.append((nx, ny))

def colorChange(graph):
    for i in range(N):
        for j in range(N):
            if graph[i][j] == "G":
                graph[i][j] = "R"
    return graph

if __name__ == "__main__":
    N = int(input())
    graph = [list(input().strip()) for _ in range(N)]
    
    visited = [[False] * N for _ in range(N)]
    normal = 0
    for i in range(N):
        for j in range(N):
            if visited[i][j] == False:
                BFS(i, j, graph, visited)
                normal += 1
    
    graph = colorChange(graph)
    visited = [[False] * N for _ in range(N)]
    colorless = 0
    for i in range(N):
        for j in range(N):
            if visited[i][j] == False:
                BFS(i, j, graph, visited)
                colorless += 1

    print(normal, colorless)

➡ 차이가 없나 했는데 메모리에서 조금 차이가 있었다. 웬만하면 전역보단 지역변수를 사용하려 하지만 함수 인자가 너무 늘어나서 귀찮기도 한데 유념해야겠다.

 

2. 또 궁금해서 visited를 재활용하고 BFS 함수를 하나 더 만들어봤다.

from collections import deque
from sys import stdin
input = stdin.readline

def BFS(x, y, graph, visited):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    q = deque([(x, y)])
    visited[x][y] = True
    while q:
        cx, cy = q.popleft()
        for d in range(4):
            nx = cx + dx[d]
            ny = cy + dy[d]
            if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == False:
                if graph[cx][cy] == graph[nx][ny]:
                    visited[nx][ny] = True
                    q.append((nx, ny))

def BFS2(x, y, graph, visited):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    q = deque([(x, y)])
    visited[x][y] = False
    while q:
        cx, cy = q.popleft()
        for d in range(4):
            nx = cx + dx[d]
            ny = cy + dy[d]
            if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == True:
                if graph[cx][cy] == graph[nx][ny]:
                    visited[nx][ny] = False
                    q.append((nx, ny))

def colorChange(graph):
    for i in range(N):
        for j in range(N):
            if graph[i][j] == "G":
                graph[i][j] = "R"
    return graph

if __name__ == "__main__":
    N = int(input())
    graph = [list(input().strip()) for _ in range(N)]
    
    visited = [[False] * N for _ in range(N)]
    normal = 0
    for i in range(N):
        for j in range(N):
            if visited[i][j] == False:
                BFS(i, j, graph, visited)
                normal += 1
    
    graph = colorChange(graph)
    colorless = 0
    for i in range(N):
        for j in range(N):
            if visited[i][j] == True:
                BFS2(i, j, graph, visited)
                colorless += 1

    print(normal, colorless)

➡ 중복되는 코드가 많아서 별로긴 하지만 결과가 궁금했는데 메모리는 늘고 시간은 줄어들었다. 나는 list를 재활용하는게 메모리에 좋을 것이라고 생각했는데 보통 메모리는 늘어나고 시간은 줄어든다... 다른 문제에서도 그랬음... 새로운 리스트 만드는 것보다 덮어쓰는게 메모리가 더 비효율적인가보다.

저작자표시

'코딩 테스트 스터디 > 백준' 카테고리의 다른 글

[골드 V] 15686번. 치킨 배달  (3) 2022.10.04
[실버 III] 9342번. 염색체  (0) 2022.10.03
[실버 I] 2156번. 포도주 시식  (1) 2022.09.15
[실버 III] 17390번. 이건 꼭 풀어야 해!  (0) 2022.09.11
[실버 II] 4096번. 수익  (0) 2022.09.09

'코딩 테스트 스터디/백준'의 다른글

  • 현재글[골드 V] 10026번. 적록색약

관련글

댓글

티스토리툴바