[DFS] 백준 1743. 음식물 피하기

 

문제

가장 큰 대륙을 찾으면 된다. 음쓰 한번에 많이 모여져 있는거 max값 출력.

초기 코드

import sys
sys.stdin =open('in.txt','rt')
input = sys.stdin.readline
sys.setrecursionlimit(10**6)  # 재귀함수 깊이 제한 풀기

dx = [1,-1,0,0]
dy = [0,0,1,-1]
def DFS(x,y):
    cnt = 1
    for i in range(4):
        xx = x+dx[i]
        yy = y+dy[i]

        if xx < 1 or yy < 1 or xx > n or yy > m:
            return cnt
        if g[xx][yy] == 1:
            cnt+= DFS(xx,yy)
            g[xx][yy] = 0

    return cnt


# n 세로길이, m 가로길이, k 음쓰개수
n, m, k = map(int, input().split())
g = [[0]*(m+1) for _ in range(n+1)]
for _ in range(k):
    r,c = map(int, input().split())
    g[r][c] = 1
print(g)

res = 0
for i in range(1,n+1):
    for j in range(1,m+1):
        if g[i][j]==1:
            cnt = 1
            g[i][j] = 0
            res = max(res,DFS(i,j))
print(res)

 

어려운점

역시나 좌표값과 범위가 헷갈린다. 왜 이전 문제랑 다르게 받은 좌표를 반대로 쓰는지 모르겠다. (graph[x][y] 랑 graph[y][x] 구분해서 쓰는지 모르겠다.)

 

정답코드

import sys
sys.setrecursionlimit(10**4)	# recursion limit 제한 설정

# 하 좌 상 우
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]


def dfs(x, y):
    global ch_matrix, matrix
    ch_matrix[x][y] = 1		# 현재 위치 체크
    cnt = 1			# 현재 위치의 크기 1

    for d in range(4):		# 현재 위치 기준으로 하,좌,상,우 탐색
        nx = x + dx[d]		# 탐색할 좌표
        ny = y + dy[d]
        
        # 탐색할 좌표가 지도를 벗어나지 않고, 값이 #이고, 이미 탐색한 곳이 아니라면
        if 0 <= nx < N and 0 <= ny < M and matrix[nx][ny] == '#' and ch_matrix[nx][ny] == 0:
            ch_matrix[nx][ny] = 1	# 좌표 체크
            cnt += dfs(nx, ny)		# dfs 실행 후 값을 cnt에 추가
    return cnt 			# 모두 탐색 후 합한 값을 리턴


# 입력 받음
N, M, K = map(int, input().split())
garbage = [tuple(map(int, input().split())) for _ in range(K)]

# 지도 생성
matrix = []			
for _ in range(N):
    matrix.append(['.' for _ in range(M)])
for x, y in garbage:
    matrix[x-1][y-1] = '#'
    
largest = 0			# 가장 큰 음쓰 크기

# 탐색 확인용 지도 생성
ch_matrix = []			
for _ in range(N):
    ch_matrix.append([0 for _ in range(M)])

# 지도에서 음쓰 위치 탐색
for x in range(N):
    for y in range(M):
        # 음쓰 탐색한 경우
        if matrix[x][y] == '#' and ch_matrix[x][y] == 0:
            ch_matrix[x][y] = 1	# 음쓰 위치 체크
            largest = max(largest, dfs(x, y))	# dfs 후 largest 값과 비교 후 저장.

print(largest)			# 출력