백준 4993번
https://www.acmicpc.net/problem/4993

문제

후기

⏰ 풀이시간 30분 ++⏰

맞힌 사람이 많지 않은 그래프 문제를 풀기 위해 풀은 사람이 적은 순으로 정렬해서

찾은 문제의 2번째다.

마찬가지로 영어로 되어있는 문제라 우선 입출력을 봐서 감을 잡고 문제의 의미를 파악하기 시작했다.

문제의 결론을 이야기 하자면,
"@" 가 그래프를 돌아다니며 몇개의 "."을 방문할 수 있는가

에 관한 문제다. ** 단, @ 본인도 방문한 횟수에 포함한다. << 결과값은 항상 1보다 크거나 같다.

@를 만나면 DFS가 시작되고, 최종적으로 몇개의 "."을 방문했는지에 대한 결과를

출력하면 되는 문제다.

나의 풀이

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

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

def dfs(x,y):
    global result
    visited[x][y] = True #@를 방문처리하고 시작

    for i in range(4): #상하좌우
        nx = x + dx[i]
        ny = y + dy[i]
        if nx<=-1 or nx>=M or ny<=-1 or ny>=N or graph[nx][ny] =="#" or graph[nx][ny] =="@": # #으로 막혀있거나, 맵을나가거나, @를 만나면 DFS는 실행되지않음
            continue

        if graph[nx][ny] =="." and not visited[nx][ny]: #.을 만났고 방문한적없으면
            visited[nx][ny] == True #방문처리
            dfs(nx,ny) #DFS시작
            result+=1 #결과값 증가

    return True

        
while True:
    N , M = map(int,input().split())
    result = 0
    if N == 0 and M==0:
        break
    graph = []
    visited= [[False]* N for _ in range(M)]
    for _ in range(M):
        graph.append(list(map(str,input().rstrip())))
    for i in range(M):
        for j in range(N):
            if graph[i][j]=="@" and not visited[i][j]: #@를 만나면 시작된다.
                dfs(i,j)
                visited[i][j]= True
    
    print(result+1) #@까지 포함해야 하므로 결과값 1 증가