[백준1926] 그림

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

 

문제 해결 방법

 

그림 정보가 적힌 좌표를 순회한다. 대신 방문여부를 알 수 있는 visited 배열이 필요하다. 

좌표를 순회할때 1을 만나고, 방문한 적이 없으면 bfs함수를 실행한다. 

이때, deque를 활용해 큐를 만들고 큐에 bfs함수를 실행할 당시의 좌표값을 넣어준다. 

bfs함수에서는 큐에서 값을 꺼내어 방문처리를 해주고, 자신의 자리에서 그림이 이어져 있다는 판단 기준인 위, 아래, 양옆을 조회 한다. 

이때, 새로 조회하는 위치가 그림 정보가 적힌 좌표의 범위를 벗어나서도 안되고, 이미 방문 한 적이 있어도 안된다. 또한 0이여도 안된다. 

값이 0이 아니고 방문한 적이 없으면 현재자리의 값에서+1을 해준다.  큐에 해당 좌표와 얼마나 끊기지 않고 값을 조회하고있는지에 대한 값 현재 자리의 값+1을 넣어준다. 

 

순회를 하면서 더이상 큐에 값을 이어 넣을 수 없으면(그림이 끊기면), 얼마나 끊기지 않고 값을 조회했는지에 대한 값을 임의의 리스트에 넣어준다. 

 

그림 정보 순회가 모두 끝나면 임의의 리스트의 원소의 개수와 원소의 최대값을 출력한다. 

 

코드 구현

정답 코드 

import sys
input=sys.stdin.readline
n, m = map(int, input().split())
from collections import deque

if n==0 and m==0:
    print(0)
    print(0)
    exit(0)

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

tmp=[]
for i in range(n):
    tmp2=list(map(int, input().split()))
    tmp.append(tmp2)

# 그냥 카운트만 하는애 cnt
# 방문 확인용 visited
cnt = 0
visited = [([False] * m) for _ in range(n)]
bigN = 0
def bfs(cnt, dequeA, visited):
    bigN=1
    while dequeA:
        yy, xx, _ = dequeA.popleft()
        visited[yy][xx] = True
        for i in range(4): 
            nx=xx+dx[i]
            ny=yy+dy[i]

            if ny<0 or nx<0 or ny>=n or nx>=m:
                continue
            if visited[ny][nx]==True or tmp[ny][nx]==0:
                continue
            if tmp[ny][nx]>=1 and visited[ny][nx]==False:
                tmp[ny][nx] = bigN+1
                bigN=bigN+1
                visited[ny][nx]=True
                dequeA.append([ny,nx, bigN])
    return cnt, bigN

tmp3=[]
check = 0
dequeA = deque()
for i in range(n):
    for j in range(m):
        if tmp[i][j] == 1 and visited[i][j] == False:
            dequeA.append([i,j, 1])
            cnt+=1
            cnt, bigN = bfs(cnt, dequeA, visited)
            tmp3.append(bigN)
            check =1

print(cnt)

if n == 0 and m ==0 or check ==0:
    print(0)
else:
    print(max(tmp3))

 

시간/공간 복잡도

따로 생각하지 않았다. 

 

최적화 및 개선

• 따로 하지않음

 

어려웠던 점

• BFS 문제를 효율적으로 푸는 방법이 가물가물해서 문제 풀기 어려웠다. 

 

알게된 것

 

함수 객체 할당과 함수 호출 구문을 구분하지 못해서 생긴 일 

 

여러줄을 받을 때 속도 감소를 위해 input()함수 말고 sys 에서 제공하는 readline()함수를 사용하려는 상황이다. 

import sys

n, m = map(int, input().split())

input=sys.stdin.readline()

tmp=[]
for i in range(n):
    
    # tmp2=list(input.split())
    tmp2=input.split()
    print('tmp2', tmp2)
    tmp.append(tmp2)

print(tmp)

 

문제가 있는 코드: 이코드에서는 2번째줄 3번째줄만 입력을 받는게 된다. 

 

• 괄호를 붙이지 않은 경우 (input = sys.stdin.readline):
  • 이 경우 sys.stdin.readline 함수 객체를 input이라는 변수에 직접 할당하는 것이다. 이 상태에서는 input은 함수 객체 자체를 참조하게 된다.
• 괄호를 붙인 경우 (input()):
  • 괄호를 붙이면 함수가 실제로 호출된다. 함수 호출은 해당 함수가 수행하는 작업을 실행하고, 그 결과를 반환한다. 

 

import sys

n, m = map(int, input().split())

input=sys.stdin.readline

tmp=[]
for i in range(n):
    
    tmp2=input().split()
    tmp.append(tmp2)

print(tmp)

문제 인지후 바꾼 코드