[백준/9252] 음식물 피하기 | 배운 점이 많은 문제

1743 음식물 피하기

알고리즘

그냥 dfs로 푸는데 cnt 처리방식 구현이 쉽게 떠오르지 않아서 고민을 좀 했다.

바로 이 부분

def dfs(x,y) : 
    
    cnt = 1
    visited[x][y] = True
    
    for dx, dy in d :
        nx, ny = x+dx, y+dy
        
        # 여기가 연결되는 부분이니까 cnt += 1 처리를 해주고, 
        if 0 <= nx < n and 0 <= ny < m:
            if graph[nx][ny] == '#' and visited[nx][ny] == False :
                visited[nx][ny] = True
                cnt += dfs(nx,ny)
    return cnt

 

이 문제에서 dfs 함수는 #를 발견하면 주변(d 좌표)을 탐색하면서 같은 영역에 속하는 곳의 크기가 얼마인지 세어주는 함수이다. 따라서 if문 조건은 주변 영역에서 계속 #이 이어지는 경우이므로, 이때 개수를 세어주어야 한다.

 

처음에 잘 생각이 안나서 cnt += 1 이런식으로 세어주고 return했는데 그러면.. 같은 영역마다 return 돼서 cnt에 누적이 되는 게 아니라 오답을 도출한다ㅠㅡㅠ

 

그래서 위와 같이 dfs(x,y)가 return 하는 값을 cnt에 누적해주면! 같은 영역에 속하는 #의 개수를 셀 수 있다.

 

전체코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m, k = map(int, input().split())
graph = [['.' for _ in range(m)] for _ in range(n)]
d = [(0,1), (0,-1), (1,0), (-1,0)]
visited = [[False for _ in range(m)] for _ in range(n)]

def dfs(x,y) : 
    
    cnt = 1
    visited[x][y] = True
    
    for dx, dy in d :
        nx, ny = x+dx, y+dy
        
        # 여기가 연결되는 부분이니까 cnt += 1 처리를 해주고, 
        if 0 <= nx < n and 0 <= ny < m:
            if graph[nx][ny] == '#' and visited[nx][ny] == False :
                visited[nx][ny] = True
                cnt += dfs(nx,ny)
    return cnt 


for _ in range(k):
    r, c = map(int, input().split())
    graph[r-1][c-1] = '#'

result = 0
for x in range(n):
    for y in range(m):
        if graph[x][y] == '#' and visited[x][y] == False:
            cnt = 0
            result = max(result, dfs(x,y))
            
            
print(result)

---

알게된 점

이 문제에서 사소한 것들을 좀 많이 얻었다.

 

1. dfs할 때 방문 처리를 잘 해줘야 한다. 까딱했다가 엄청난 재귀를 생성하게된다...

2. 가로길이/세로길이 이게 너무 헷갈리는데 일반적으로 그래프 탐색 문제에서 가로/세로 길이라 함은 다음과 같다.

생각해보면 당연한 건데 처음엔 좀 많이 헷갈렸다ㅠㅠ 바본가

가로: 열 담당 그러니까 열의 개수

세로: 행 담당, 행의 개수

 

3. 지금까지 탐색한 부분 중 영역이 최대인 경우는 아래처럼 result = max(result, dfs(x,y)) 이런식으로 작성하여 max의 비교대상에 각각의 탐색 영역을 포함하는 것이다.

result = max(result, dfs(x,y))

 

여러 case 중 최대를 찾을 때 함수를 쓰게 된다면 return 값을 max의 비교 대상에 포함하자.

 

막줄이 핵심