[백준] 1926번 그림 (파이썬)

 

문제

1926번: 그림

풀이

DFS

# 방향으로 움직일 리스트
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

big = 0
def dfs(graph, x, y, visited):
    global big, c
    # 큰 값을 구해줘
    big = max(big, visited[x][y])
    # 빠지지 않고 계속 움직이면 돌아가더라도 숫자를 유지시켜줘
    c += 1

    for i in range(4):
        nx = x + dx[i] 
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m:
            if graph[nx][ny] == 1 and visited[nx][ny] == 0:
                visited[nx][ny] = c
                # 갈수 있는게 없을 때까지반복해줘
                dfs(graph, nx, ny, visited)
    

import sys
input = sys.stdin.readline
sys.setrecursionlimit(3000000)
n, m = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]
vitised = [[0] * m for _ in range(n)]

pic = 0
for x in range(n):
    for y in range(m):
        if graph[x][y] == 1:
            if vitised[x][y] == 0:
            	# 들어갈때마다 c 초기화
                c = 1
                vitised[x][y] = 1
                dfs(graph, x, y, vitised)
                # 그림이 몇개인지 세줘
                pic += 1
                

print(pic)
print(big)

해설

DFS를 사용해서 더 갈 수 있는곳이 있다면 계속 움직이도록 했다.

visited에는 움직인만큼의 값을 넣어서 visited에 들어간 값과 저장된 big 중 큰걸 비교하여는 방식으로 big을 구하고 갈 방향이 없을 때 마다 pic에 1씩 넣어줘서 그림의 개수를 구했다.

처음 만든 코드에서는

 

visited[nx][ny] = c  대신 visited[nx][ny] = visited[x][y] + 1를 사용했었는데, 이럴 경우 아래와 같은 경우 

4 5
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1

아래와 같은 상황이 발생하여 틀렸다. 그래서 c를 추가하여 갈 수 있는 곳이 있다면 계속 돌아가고 없다면 들어갈 때 다시 초기화 하는 방식으로 상황을 해결하였다.

1 2 3 0 11
2 0 4 0 10
3 0 5 0 9
4 0 6 7 8
원하는 답 big = 14
출력 값 big = 11

BFS

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

from collections import deque
def bfs(graph, x, y, visited):
    global c
    # popleft를 위해 사용해줘
    q = deque([(x, y)])
    # 처음 들어간 곳은 1
    vitised[x][y] = 1
	
    # q가 없을때까지 반복해줘
    while q:
    	# 지운 튜플 값을 저장해줘
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i] 
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 1 and visited[nx][ny] == 0:
                    c += 1
                    q.append((nx, ny))
                    visited[nx][ny] = c


import sys
input = sys.stdin.readline
sys.setrecursionlimit(3000000)
n, m = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]
vitised = [[0] * m for _ in range(n)]

pic = 0
for x in range(n):
    for y in range(m):
        if graph[x][y] == 1:
            if vitised[x][y] == 0:
                c = 0
                bfs(graph, x, y, vitised)
                pic += 1
print(pic)
# c == 0이 아니라면 처음 vistied[x][y]의 1을 더해줘
if c != 0:
    c += 1
print(c)

해설

DFS에서 기본적인 틀을 같고 c가 0인 경우 0이 나와야하기 때문에 처음 들어갈때 visited의 값을 더할 수가 없어서 마지막에 더해주었다.